Пирамидално сортиране

Пирамидално сортиране (на английски: Heapsort) е детермистичен алгоритъм за сортиране, който създава сортиран масив (или списък), и вид алгоритъм за сортиране чрез пряка селекция. Въпреки че е по-бавен, със сложност O (n log n), отколкото едно добро приложение на quicksort алгоритъм, той има предимството за по-благоприятен най-лош случай, защото не използва много масиви или рекурсия. Измислен е от J. W. J. Williams през 1964 г.[1]

Принцип на действие

редактиране

Пирамидалното сортиране може да бъде разделено на две стъпки.

Първа стъпка: създава се „купчина“ от елементи на множеството.

Втора стъпка: създава се сортиран масив, чрез взимане и премахване на най-големия елемент от пирамидална структура от данни (heap) и поставянето му в друг масив. „Купчината“ се реконструира при всяко премахване и след като всички обекти са премахнати от heap паметта, се създава пълният сортиран масив. Посоката на сортираните елементи може да бъде променена, като се избере min-heap или max-heap в първата стъпка. За да се изпълни този алгоритъм, се изискват два масива – един за елементите в купчината и втори за сортирания масив.

Пирамидалното сортиране може да бъде извършено и с един масив – когато някой елемент се премахва от „купчината“, той освобождава място, и елементът може да бъде добавен в края на същия масив.

Варианти

редактиране
  • Най-важният вариант на алгоритъма за пирамидално сортиране е подобрението на R. W. Floyd, който предоставя около 25% по-висока скорост на изпълнение чрез използването на само едно сравнение при добавяне на елемент към „купчината“ и при последвалото премахване на екстремния елемент от heap-а. Този подход има по-елегантно формулиране.
  • Троичен heapsort[2] използва троичен heap, в която всеки елемент има три деца. Той е по-сложен за програмиране, защото всяка стъпка на подреждане на елементите изисква три сравнения и едно разместване, където в двоичния heap се изискват две сравнения и едно разместване. Троичният heapsort извършва две стъпки за по-малко време, отколкото двоичният heap извършва три стъпки, затова за един и същи период от време, троичният heapsort извършва повече сравнения и размествания. Трочният heapsort е с около 12% по-бърз от стандартното двоично пирамидално сортиране.
  • Гладкото сортиране (Smoothsort) [3][4] е разновидност на пирамидалното сортиране. Алгоритъмът е разработен от Edsger Dijkstra през 1981. Както при heapsort, горната граница на smoothsort-а е O(n log n). Предимствата му са, че е по-близо до скорост O(n), ако данните са сортирани до някаква степен, където скоростта на heapsort е около O(n log n) независимо от степента на сортиране. Поради сложността на алгоритъма, smoothsort се използва рядко.
  • Levcopoulos и Petersson[5] описват разновидност на пирамидалното сортиране, основана на a декартово дърво, което не добавя елемент към „купчината“ докато по-малките стойности от двете му страни не са били вече включени в сортирания втори масив. Както те показват, тази модификация може да позволи на алгоритъма да сортира по-бързо от O(n log n) за входни данни, които са близки до сортирани.

Сравнение с други алгоритми за сортиране

редактиране

Heapsort е конкуриран главно от quicksort, друг високо ефективен сортиращ алгоритъм с общо приложение.

Quicksort е по-бърз от heapsort, но най-лошият случай на quicksort е O(n2), което е неприложимо при големи множества от данни. Също така може да бъде прочетена информация за имплементацията на алгоритъма, което само по себе си създава риск за сигурността. Ето защо вградени системи с ограничения в реално време или системи, за които е ключова сигурността, често използват пирамидалното сортиране.

Алтернатива на heapsort е сортирането чрез сливане, който има същите граници на скоростта на изпълнение. Сортирането чрез сливане изисква Ω(n) спомагателно място, heapsort изисква само брой константи. Heapsort стартира по-бързо при компютърни системи с малък или бавен кеш за информация. От друга страна, сортирането чрез сливане има няколко предимства пред парамидалното сортиране:

  • Сортиране чрез сливане върху масиви има значително по-добра производителност при кеша на данните, често с по-добра производителност от heapsort при нови компютри, защото merge сортирането често манипулира съседни локации в паметта, докато референциите на heapsort са разпръснати навсякъде в heap-а.
  • Heapsort не е стабилно сортиране.
  • Сортиране чрез сливане е добър паралелен алгоритъм е се доближава до линейно ускорение с лесна имплементация.
  • Сортиране чрез сливане може да бъде адаптирано за приложение при свързани листове с O(1) допълнително място.[6]
  • Сортиране чрез сливане може да бъде използвано във [външно сортиране], докато heapsort не може, заради локацията на референциите.

Introsort е интересна алтернатива на heapsort, която комбинира quicksort и heapsort, взимайки предимствата и на двата алгоритъма: скоростта в най-лош случай и средната скорост на quicksort.

Псевдокод

редактиране

Следва псевдокод за приложение на алгоритъма]. Индексирането на масивите започва от нула и размяна се използва за замяната на два елемента от масива. Движение „надолу“ означава от основата към листата или от по-малки индекси към по-големи. По време на сортирането, най-големият елемент е в основата на heap-а, с индекс a[0], докато в края на сортирането, най-големият елемент е с последна позиция в масива.

 function heapSort(a, count) is
     input:  несортиран масив a of length count
     (задава се посока на масива)
     heapify(a, count)
     end := count-1
     while end > 0 do
         (разместване на основата на heap-а с последния елемент от масива)
         swap(a[end], a[0])
         (намаляване на големината на „купчината“ с едно, така че предишната максимална стойност ще остане на мястото си
         end := end – 1
         (задава се посока на масива в max-heap)
         siftDown(a, 0, end)
 function heapify(a, count) is
     (start – добавя се индекса на последни елемент)
     start := (count – 2) / 2
     while start ≥ 0 do
         siftDown(a, start, count-1)
         start := start – 1
 function siftDown(a, start, end) is
     input:  end показва горната граница на heap-а, до която да се обхожда множеството.
     root := start
     while root * 2 + 1 ≤ end do (Докато дървото има поне едно дете)
         child := root * 2 + 1 (root*2 + 1 точки до лявото дете)
         swap := root (запазва пътя до детето за размяна.)
         (проверка дали обекта в основата е по-малък от лявото дете)
         if a[swap] < a[child]
             swap := child
         (проверява дали дясното дете съществува и дали е по-голямо от това, с което извършваме размяна)
         if child+1 ≤ end and a[swap] < a[child+1]
             swap := child + 1
         (проверка дали е необходима размяна)
         if swap != root
             swap(a[root], a[swap])
             root := swap (повторение, докато се премести детето надолу)
         else
             return

Нека { 6, 5, 3, 1, 8, 7, 2, 4 } е лист с числа, които искаме да сортираме от най-малкото към най-голямото.

 
Пример за heapsort.

1. Построяване на heap-а

Heap newly added element swap elements
nil 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3, 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1, 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1

2. Сортиране.

Heap swap elements delete element sorted array details
8, 6, 7, 4, 5, 3, 2, 1 8, 1 разместване на 8 и 1, за да изтрием 8 от heap-а
1, 6, 7, 4, 5, 3, 2, 8 8 изтриване на 8 и добавяне към сортирания масив
1, 6, 7, 4, 5, 3, 2 1, 7 8 разместване на 1 и 7
7, 6, 1, 4, 5, 3, 2 1, 3 8 разместване на 1 и 3
7, 6, 3, 4, 5, 1, 2 7, 2 8 разместване на 7 и 2, за да изтрием 7 от heap-а
2, 6, 3, 4, 5, 1, 7 7 8 изтриване на 7 и добавяне към сортирания масив
2, 6, 3, 4, 5, 1 2, 6 7, 8 разместване на 2 и 6
6, 2, 3, 4, 5, 1 2, 5 7, 8 разместване на 2 и 5
6, 5, 3, 4, 2, 1 6, 1 7, 8 разместване на 6 и 1, за да изтрием 6 от heap-а
1, 5, 3, 4, 2, 6 6 7, 8 изтриване на 6 и добавяне към сортирания масив
1, 5, 3, 4, 2 1, 5 6, 7, 8 разместване на 1 и 5
5, 1, 3, 4, 2 1, 4 6, 7, 8 разместване на 1 и 4
5, 4, 3, 1, 2 5, 2 6, 7, 8 разместване на 5 и 2, за да изтрием 5 от heap-а
2, 4, 3, 1, 5 5 6, 7, 8 изтриване на 5 и добавяне към сортирания масив
2, 4, 3, 1 2, 4 5, 6, 7, 8 разместване на 2 и 4
4, 2, 3, 1 4, 1 5, 6, 7, 8 разместване на 4 и 1, за да изтрием 4 от heap-а
1, 2, 3, 4 4 5, 6, 7, 8 изтриване на 4 и добавяне към сортирания масив
1, 2, 3 1, 3 4, 5, 6, 7, 8 разместване на 1 и 3
3, 2, 1 3, 1 4, 5, 6, 7, 8 разместване на 3 и 1, за да изтрием 3 от heap-а
1, 2, 3 3 4, 5, 6, 7, 8 изтриване на 3 и добавяне към сортирания масив
1, 2 1, 2 3, 4, 5, 6, 7, 8 разместване на 1 и 2
2, 1 2, 1 3, 4, 5, 6, 7, 8 разместване на 2 и 1, за да изтрием 3 от heap-а
1, 2 2 3, 4, 5, 6, 7, 8 изтриване на 2 и добавяне към сортирания масив
1 1 2, 3, 4, 5, 6, 7, 8 изтриване на 1 и добавяне към сортирания масив
1, 2, 3, 4, 5, 6, 7, 8 завършено
  1. Williams 1964
  2. „Data Structures Using Pascal“, 1991, page 405, gives a ternary heapsort as a student exercise. „Write a sorting routine similar to the heapsort except that it uses a ternary heap.“
  3. www.cs.utexas.edu
  4. www.cs.utexas.edu
  5. Heapsort – Adapted for Presorted Files // WADS '89: Proceedings of the Workshop on Algorithms and Data Structures. Т. 382. London, UK, Springer-Verlag, 1989. DOI:10.1007/3-540-51542-9_41. с. 499 – 509..
  6. Merge sort Wikipedia page

Източници

редактиране
    Тази страница частично или изцяло представлява превод на страницата Heapsort в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​