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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Принцип на действие[редактиране | edit source]

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

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

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

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

Варианти[редактиране | edit source]

  • Най-важният вариант на алгоритъма за пирамидално сортиране е подобрението на R. W. Floyd, който предоставя около 25% по-висока скорост на изпълнение, чрез използването на само едно сравнение при [Binary heap#Insert|добавяне]] на елемент към "купчината" и при последвалото премахване на екстремния елемент от heap-а. Още повече, този подход има по-елегантно формулиране.
  • Троичен heapsort[2] използва троичен heap, в която всеки елемент има три деца. Той е по-сложен за програмиране, защото всяка стъпка на подреждане на елементите изисква три сравнения и едно разместване, където в двоичния heap се изискват две сравнения и едно разместване. Троичният heapsort извършва две стъпки за по-малко време, от колкото двоичния heap извършва три стъпки, затова за един и същи период от време, троичният heapsort извършва повече сравнения и размествания. Трочният heapsort е с около 12% по-бърз от стандартното двоично пирамидално сортиране.
  • Smoothsort algorithm[3][4] is a variation of heapsort developed by Edsger Dijkstra in 1981. Както при heapsort, горната граница на smoothsort-а е O(n log n). Предимствата му са, че е по близо до скорост O(n), ако данните са сортирани до някаква степен, където скоростта на heapsort е около O(n log n) независимо от степента на сортиране. Поради сложността на алгоритъма, smoothsort се използва рядко.
  • Levcopoulos and Petersson[5] describe a variation of heapsort based on a Cartesian tree that does not add an element to the heap until smaller values on both sides of it have already been included in the sorted output. As they show, this modification can allow the algorithm to sort more quickly than O(n log n) for inputs that are already nearly sorted.

Сравнение с други алгоритми за сортиране[редактиране | edit source]

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.

Псевдокод[редактиране | edit source]

Следва [[псевдокод] за приложение на алгоритъма]. Индексирането на масивите започва от нула и размяна се използва за замяната на два елемента от масива. Движение "надолу" означава от основата към листата или от по-малки индекси към по-големи. По време на сортирането, най-големият елемент е в основата на 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

Пример[редактиране | edit source]

Нека { 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 завършено

Бележки[редактиране | edit source]

  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. http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF
  4. http://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html
  5. Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", „WADS '89: Proceedings of the Workshop on Algorithms and Data Structures“, Lecture Notes in Computer Science, 382, London, UK: Springer-Verlag, pp. 499–509, doi:10.1007/3-540-51542-9_41 .
  6. Merge sort Wikipedia page

Източници[редактиране | edit source]

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