Pyramide sortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. februar 2020; checks kræver 9 redigeringer .

Heap sort ( eng. Heapsort , "Heap sort" [1] ) er en sorteringsalgoritme , der fungerer i det værste, i gennemsnit og i det bedste tilfælde (det vil sige garanteret) til operationer ved sortering af elementer. [2] Mængden af brugt backend-hukommelse afhænger ikke af størrelsen af arrayet (det vil sige ). $O(n\log n)$ $n$ $O(1)$

Kan opfattes som en forbedring af boblesortering , hvor et element flyder ( min-heap ) / synker ( max-heap ) over mange stier.

Oprettelseshistorie

Heapsort blev foreslået af J. Williams i 1964. [en]

Algoritme

Heapsort bruger et binært sorteringstræ . Et sorteringstræ er et træ, der opfylder følgende betingelser:

Hvert blad har en dybde på enten , eller , som er træets maksimale dybde. $d$ $d-1$ $d$
Værdien ved ethvert toppunkt er ikke mindre (den anden mulighed er ikke mere end) værdien af dens efterkommere.

En bekvem datastruktur for et sorteringstræ er en matrix Array, som Array[0] er elementet ved roden, og elementets børn Array[i]er Array[2i+1]og Array[2i+2].

Sorteringsalgoritmen vil bestå af to hovedtrin:

1. Byg elementerne i arrayet i form af et sorteringstræ :

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

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

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

Dette trin kræver operation. $På)$

2. Vi fjerner elementer fra roden et ad gangen og genopbygger træet. Det vil sige, ved det første trin udveksler vi Array[0]og Array[n-1]transformerer Array[0], Array[1], … , Array[n-2]til et sorteringstræ. Derefter omarrangerer vi Array[0]og Array[n-2], transformerer Array[0], Array[1], … , Array[n-3]til et sorteringstræ. Processen fortsætter, indtil der kun er ét element tilbage i sorteringstræet. Så Array[0]er , Array[1], … , Array[n-1] en ordnet sekvens.

Dette trin kræver operation. $O(n\log n)$

Fordele og ulemper

Fordele

Har en dokumenteret worst case bundet . $O(n\cdot\log n)$
Sortering på plads, det vil sige, kræver kun O (1) ekstra hukommelse (hvis træet er organiseret som vist ovenfor).

Fejl

Ustabil - For at sikre stabilitet skal du udvide nøglen.
På næsten sorterede arrays tager det lige så lang tid som på kaotiske data.
På et trin skal udvælgelsen foretages tilfældigt over hele længden af arrayet - derfor kan algoritmen ikke kombineres godt med caching og hukommelsesswap .
Metoden kræver "øjeblikkelig" direkte adgang; virker ikke på sammenkædede lister og andre strukturer for sekventiel adgangshukommelse.
Parallellerer ikke.

O ( n ) hukommelseskrævende flettesortering er hurtigere ( med en mindre konstant) og forringes ikke på dårlige data. $O(n\cdot\log n)$

På grund af kompleksiteten af algoritmen opnås forstærkningen kun for store n . På lille n (op til flere tusinde) er Shellsort hurtigere .

Ansøgning

Algoritmen "heap sort" bruges aktivt i Linux-kernen .

Noter

↑ 1 2 Forelæsningsforløb "Moderne teknologier til parallel programmering", Foredrag nr. 5: Heap sort (utilgængeligt link) . Hentet 20. marts 2009. Arkiveret fra originalen 15. marts 2009. (ubestemt)
↑ ScienceDirect - Journal of Algorithms: The Analysis of Heapsort . Hentet 30. september 2017. Arkiveret fra originalen 4. juni 2012. (ubestemt)

Litteratur

Levitin A.V. Kapitel 6. Transformationsmetode: Dynger og dynger // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 275-284. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 6. Heapsort // Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - S. 182-188. — ISBN 5-8459-0857-4 .

Links

Heap sort - en detaljeret beskrivelse med illustrationer og et eksempel på implementering i C ++. Udledningen af estimater af algoritmens hastighed og måling af køretiden på et rigtigt computersystem er givet.
Sortering ved hjælp af en heap (heap sort) - en forståelig beskrivelse med illustrationer og et eksempel på implementering i Pascal.
Dynamic Visualization 7 Open Source sorteringsalgoritmer Arkiveret 20. september 2017 på Wayback Machine

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom