Пирамидално сортиране () е детермистичен алгоритъм за сортиране, който създава сортиран масив (или списък), и вид алгоритъм за сортиране чрез пряка селекция. Въпреки че е по-бавен, със сложност O (n log n), отколкото едно добро приложение на quicksort алгоритъм, той има предимството за по-благоприятен най-лош случай, защото не използва много масиви или рекурсия. Измислен е от J. W. J. Williams през 1964 г.
Принцип на действие Пирамидалното сортиране може да бъде разделено на две стъпки.
Първа стъпка: създава се „купчина“ от елементи на множеството.
Втора стъпка: създава се сортиран масив, чрез взимане и премахване на най-големия елемент от пирамидална структура от данни (heap) и поставянето му в друг масив. „Купчината“ се реконструира при всяко премахване и след като всички обекти са премахнати от heap паметта, се създава пълният сортиран масив. Посоката на сортираните елементи може да бъде променена, като се избере min-heap или max-heap в първата стъпка. За да се изпълни този алгоритъм, се изискват два масива – един за елементите в купчината и втори за сортирания масив.
Пирамидалното сортиране може да бъде извършено и с един масив – когато някой елемент се премахва от „купчината“, той освобождава място, и елементът може да бъде добавен в края на същия масив.
Варианти Най-важният вариант на алгоритъма за пирамидално сортиране е подобрението на R. W. Floyd, който предоставя около 25% по-висока скорост на изпълнение чрез използването на само едно сравнение при добавяне на елемент към „купчината“ и при последвалото премахване на екстремния елемент от heap-а. Този подход има по-елегантно формулиране. Троичен heapsort„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.“ използва троичен heap, в която всеки елемент има три деца. Той е по-сложен за програмиране, защото всяка стъпка на подреждане на елементите изисква три сравнения и едно разместване, където в двоичния heap се изискват две сравнения и едно разместване. Троичният heapsort извършва две стъпки за по-малко време, отколкото двоичният heap извършва три стъпки, затова за един и същи период от време, троичният heapsort извършва повече сравнения и размествания. Трочният heapsort е с около 12% по-бърз от стандартното двоично пирамидално сортиране. Гладкото сортиране (Smoothsort) www.cs.utexas.eduwww.cs.utexas.edu е разновидност на пирамидалното сортиране. Алгоритъмът е разработен от Edsger Dijkstra през 1981. Както при heapsort, горната граница на smoothsort-а е O(n log n). Предимствата му са, че е по-близо до скорост O(n), ако данните са сортирани до някаква степен, където скоростта на heapsort е около O(n log n) независимо от степента на сортиране. Поради сложността на алгоритъма, smoothsort се използва рядко. Levcopoulos и Petersson. описват разновидност на пирамидалното сортиране, основана на a декартово дърво, което не добавя елемент към „купчината“ докато по-малките стойности от двете му страни не са били вече включени в сортирания втори масив. Както те показват, тази модификация може да позволи на алгоритъма да сортира по-бързо от O(n log n) за входни данни, които са близки до сортирани.
Сравнение с други алгоритми за сортиране Heapsort е конкуриран главно от quicksort, друг високо ефективен сортиращ алгоритъм с общо приложение.
Quicksort е по-бърз от heapsort, но най-лошият случай на quicksort е O(n2), което е неприложимо при големи множества от данни. Също така може да бъде прочетена информация за имплементацията на алгоритъма, което само по себе си създава риск за сигурността. Ето защо вградени системи с ограничения в реално време или системи, за които е ключова сигурността, често използват пирамидалното сортиране.
Алтернатива на heapsort е сортирането чрез сливане, който има същите граници на скоростта на изпълнение. Сортирането чрез сливане изисква Ω(n) спомагателно място, heapsort изисква само брой константи. Heapsort стартира по-бързо при компютърни системи с малък или бавен кеш за информация. От друга страна, сортирането чрез сливане има няколко предимства пред парамидалното сортиране:
Сортиране чрез сливане върху масиви има значително по-добра производителност при кеша на данните, често с по-добра производителност от heapsort при нови компютри, защото merge сортирането често манипулира съседни локации в паметта, докато референциите на heapsort са разпръснати навсякъде в heap-а. Heapsort не е стабилно сортиране. Сортиране чрез сливане е добър паралелен алгоритъм е се доближава до линейно ускорение с лесна имплементация. Сортиране чрез сливане може да бъде адаптирано за приложение при свързани листове с O(1) допълнително място.Merge sort Wikipedia page Сортиране чрез сливане може да бъде използвано във [външно сортиране], докато heapsort не може, заради локацията на референциите.
Introsort е интересна алтернатива на heapsort, която комбинира quicksort и heapsort, взимайки предимствата и на двата алгоритъма: скоростта в най-лош случай и средната скорост на quicksort.
Псевдокод Следва псевдокод за приложение на алгоритъма]. Индексирането на масивите започва от нула и размяна се използва за замяната на два елемента от масива. Движение „надолу“ означава от основата към листата или от по-малки индекси към по-големи. По време на сортирането, най-големият елемент е в основата на heap-а, с индекс a, докато в края на сортирането, най-големият елемент е с последна позиция в масива. 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) (намаляване на големината на „купчината“ с едно, така че предишната максимална стойност ще остане на мястото си 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 } е лист с числа, които искаме да сортираме от най-малкото към най-голямото.
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 завършено
Бележки
Източници
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapters 6 and 7 Respectively: Heapsort and Priority Queues A PDF of Dijkstra's original paper on Smoothsort Heaps and Heapsort Tutorial by David Carlson, St. Vincent College Heaps of Knowledge
Категория:Алгоритми