Sortare piramidală

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 februarie 2020; verificările necesită 9 modificări .

Heap sort ( ing. Heapsort , „Heap sort” [1] ) este un algoritm de sortare care funcționează în cel mai rău, în medie și în cel mai bun caz (adică garantat) pentru operațiunile de sortare a elementelor. [2] Cantitatea de memorie back-end utilizată nu depinde de dimensiunea matricei (adică, ). $O(n\log n)$ $n$ $O(1)$

Poate fi considerată o îmbunătățire a sortării cu bule , în care un element plutește ( min-heap ) / se scufundă ( max-heap ) pe mai multe căi.

Istoricul creației

Heapsort a fost propus de J. Williams în 1964. [unu]

Algoritm

Heapsort folosește un arbore de sortare binar . Un arbore de sortare este un arbore care îndeplinește următoarele condiții:

Fiecare frunză are o adâncime de , sau , care este adâncimea maximă a copacului. $d$ $d-1$ $d$
Valoarea la orice vârf nu este mai mică (cealaltă opțiune nu este mai mare decât) valoarea descendenților săi.

O structură de date convenabilă pentru un arbore de sortare este o matrice Arrayastfel încât să Array[0] fie elementul de la rădăcină, iar copiii elementului Array[i]sunt Array[2i+1]și Array[2i+2].

Algoritmul de sortare va consta din doi pași principali:

1. Construiți elementele matricei sub forma unui arbore de sortare :

${\text{Matrice}}[i]\geq {\text{Matrice}}[2i+1]$

${\text{Matrice}}[i]\geq {\text{Matrice}}[2i+2]$

la . $0\leq i<n/2$

Acest pas necesită intervenție chirurgicală. $Pe)$

2. Vom elimina elementele din rădăcină pe rând și vom reconstrui arborele. Adică, la primul pas, schimbăm Array[0]și Array[n-1], transformăm Array[0], Array[1], … , Array[n-2]într-un arbore de sortare. Apoi rearanjam Array[0]și Array[n-2], transformăm Array[0], Array[1], ... , Array[n-3]într-un arbore de sortare. Procesul continuă până când rămâne un singur element în arborele de sortare. Atunci Array[0], Array[1], … , Array[n-1] este o secvență ordonată.

Acest pas necesită intervenție chirurgicală. $O(n\log n)$

Avantaje și dezavantaje

Avantaje

Are un caz dovedit legat de cel mai rău caz . $O(n\cdot\log n)$
Sortează în loc, adică necesită doar O (1) memorie suplimentară (dacă arborele este organizat așa cum se arată mai sus).

Defecte

Instabil - Pentru a asigura stabilitatea, trebuie să extindeți cheia.
Pe matrice aproape sortate, durează atât timp cât în cazul datelor haotice.
La un singur pas, selecția trebuie făcută aleatoriu pe toată lungimea matricei - prin urmare, algoritmul nu se combină bine cu stocarea în cache și schimbarea memoriei .
Metoda necesită acces direct „instantaneu”; nu funcționează pe listele legate și alte structuri de memorie cu acces secvenţial.
Nu se paralelizează.

O ( n ) sortare de îmbinare consumatoare de memorie este mai rapidă ( cu o constantă mai mică) și nu se degradează pe datele proaste. $O(n\cdot\log n)$

Datorită complexității algoritmului, câștigul se obține numai pentru n mare . Pe n mic (până la câteva mii), Shellsort este mai rapid .

Aplicație

Algoritmul „sortare heap” este utilizat în mod activ în nucleul Linux .

Note

↑ 1 2 Curs de prelegeri „Tehnologii moderne de programare paralelă”, Lectura nr. 5: Sortare heap (link inaccesibil) . Consultat la 20 martie 2009. Arhivat din original pe 15 martie 2009. (nedefinit)
^ ScienceDirect - Journal of Algorithms: The Analysis of Heapsort . Consultat la 30 septembrie 2017. Arhivat din original pe 4 iunie 2012. (nedefinit)

Literatură

Levitin A.V. Capitolul 6. Metoda de transformare: Heaps and Heapsort // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 275-284. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capitolul 6. Heapsort // Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - S. 182-188. — ISBN 5-8459-0857-4 .

Link -uri

Heap sort - o descriere detaliată cu ilustrații și un exemplu de implementare în C++. Sunt date estimări ale vitezei algoritmului și măsurarea timpului de rulare pe un sistem de calcul real.
Sortare folosind un heap (heap sort) - o descriere inteligibilă cu ilustrații și un exemplu de implementare în Pascal.
Dynamic Visualization 7 algoritmi de sortare open source arhivat 20 septembrie 2017 la Wayback Machine

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet