9. Сортиране - общи положения; сортиране чрез сравнение

** Класификации на алгоритмите за сортиране [Глава 3, стр.187]

* В зависимост от местонахождението на данните:
- вътрешно (директен достъп), например бързо сортиране и
- външно (последователен достъп), например сливане.
* В зависимост от операцията:
- чрез сравнение (<, > и ==) на двойки елементи и
- чрез трансформация, напр. сортиране чрез броене.
* Свойство на алгоритъма за сортиране:
- устойчиви - относителният ред на елементите с равни ключове остава непроменен и
- неустойчиви - разместване на елементи с равни ключове.
* Ефективност на алгоритмите за сортиране - брой на извършени сравнения и размени (присвоявания).
* Използване на допълнителна памет.

** Дърво на сравненията; сортиране на 3 числа.

** Класически универсални елементарни методи за сортиране чрез сравнение O(n²):
- пряко вмъкване - намираме елемент, който "не е сортиран" и го поставяме на мястото му в сортираната част;
- пряка селекция (избор) - намираме най-малкия елемент и го поставяме на мястото му в окончателно сортираната част;
- мехурчето - последователно се разглеждат двойки елементи и евентуално се разменят.

** Бързо сортиране на Хоор - O(n log₂n) средно и O(n²) в най-лошия случай.

** Пирамидално сортиране O(n log₂n) и тази оценка не може да се подобри при сортиране чрез сравняване.

Задача 9. МНОГО ПРАВОЪГЪЛНИЦИ
    Дадени са n правоъгълници в равнината със страни, успоредни на координатните оси и с координати на върховете – цели числа. Напишете програма, която намира лицето на сечението на всички правоъгълници и лицето на обединението им.

    Вход
    Първото число от стандартния вход задава броя на примерите. Всеки пример се описва с броя на правоъгълниците n - цяло положително число по-малко от 1000 и координатите на горния ляв и долния десен ъгъл на правоъгълника, които са цели числа между -1000 и +1000 включително.

    Изход
    За всеки пример на отделен ред на стандартния изход се извеждат две числа – лицата на сечението и обединението на правоъгълниците.

    ПРИМЕР

Вход
2
2
-10 10 10 -10
0 20 20 0
3
0 1 1 0
-1 0 0 -1
0 0 1 -1

Изход
100 700
0 3