Пирамидално сортиране
Тази статия се нуждае от подобрение. Необходимо е: форматиране. Ако желаете да помогнете на Уикипедия, използвайте опцията редактиране в горното меню над статията, за да нанесете нужните корекции. |
Пирамидално сортиране (на английски: 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 } е лист с числа, които искаме да сортираме от най-малкото към най-голямото.
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 | завършено |
Бележки
редактиране- ↑ Williams 1964
- ↑ „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.“
- ↑ www.cs.utexas.edu
- ↑ www.cs.utexas.edu
- ↑ 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..
- ↑ Merge sort Wikipedia page
Източници
редактиране- Williams, J. W. J. Algorithm 232 – Heapsort. Communications of the ACM. Т. 7. 1964. с. 347 – 348.
- Floyd, Robert W. Algorithm 245 – Treesort 3. Communications of the ACM. Т. 7. 1964. с. 701.
- Carlsson, Svante. Average-case results on heapsort. BIT. Т. 27. 1987. с. 2 – 17.
- Knuth, Donald. §5.2.3, Sorting by Selection // Sorting and Searching. third. Т. 3. Addison-Wesley, 1997. ISBN 0-201-89685-0. с. 144 – 155.
- 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 Архив на оригинала от 2012-11-06 в Wayback Machine.
 
|
Тази страница частично или изцяло представлява превод на страницата Heapsort в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |