Pyramid sort

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 februari 2020; kontroller kräver 9 redigeringar .

Heap sort ( eng. Heapsort , "Heap sort" [1] ) är en sorteringsalgoritm som fungerar i sämsta fall, i genomsnitt och i bästa fall (det vill säga garanterat) för operationer vid sortering av element. [2] Mängden använt back-end-minne beror inte på storleken på arrayen (det vill säga ). $O(n\log n)$ $n$ $O(1)$

Kan ses som en förbättring av bubble sort , där ett element flyter ( min-heap ) / sjunker ( max-heap ) över många banor.

Skapande historia

Heapsort föreslogs av J. Williams 1964. [ett]

Algoritm

Heapsort använder ett binärt sorteringsträd . Ett sorteringsträd är ett träd som uppfyller följande villkor:

Varje blad har ett djup på antingen , eller , vilket är trädets maximala djup. $d$ $d-1$ $d$
Värdet vid någon vertex är inte mindre (det andra alternativet är inte mer än) värdet på dess avkomlingar.

En bekväm datastruktur för ett sorteringsträd är en array Arraysom Array[0] är elementet vid roten och elementets barn Array[i]är Array[2i+1]och Array[2i+2].

Sorteringsalgoritmen kommer att bestå av två huvudsteg:

1. Bygg elementen i arrayen i form av ett sorteringsträd :

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

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

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

Detta steg kräver operation. $På)$

2. Vi tar bort element från roten ett i taget och bygger om trädet. Det vill säga, i det första steget byter vi Array[0]och Array[n-1]omvandlar Array[0], Array[1], ... , Array[n-2]till ett sorteringsträd. Sedan arrangerar vi om Array[0]och Array[n-2], transformerar Array[0], Array[1], … , Array[n-3]till ett sorteringsträd. Processen fortsätter tills det bara finns ett element kvar i sorteringsträdet. Sedan Array[0], Array[1], … , Array[n-1] är en ordnad sekvens.

Detta steg kräver operation. $O(n\log n)$

Fördelar och nackdelar

Fördelar

Har ett bevisat värsta fall bundet . $O(n\cdot\log n)$
Sorterar på plats, det vill säga kräver endast O (1) extra minne (om trädet är organiserat enligt ovan).

Brister

Instabil - För att säkerställa stabilitet måste du utöka nyckeln.
På nästan sorterade arrayer tar det lika lång tid som på kaotiska data.
I ett steg måste valet göras slumpmässigt över hela längden av arrayen - därför kombineras algoritmen inte bra med cachning och minnesbyte .
Metoden kräver "omedelbar" direktåtkomst; fungerar inte på länkade listor och andra strukturer för sekventiell åtkomst.
Parallellerar inte.

O ( n ) minneskrävande sammanslagningssortering är snabbare ( med en mindre konstant) och försämras inte på dålig data. $O(n\cdot\log n)$

På grund av algoritmens komplexitet erhålls förstärkningen endast för stora n . På litet n (upp till flera tusen) är Shellsort snabbare .

Applikation

Algoritmen "heap sort" används aktivt i Linux-kärnan .

Anteckningar

↑ 1 2 Föreläsningskurs "Modern teknologier för parallell programmering", Föreläsning nr 5: Heap sort (otillgänglig länk) . Hämtad 20 mars 2009. Arkiverad från originalet 15 mars 2009. (obestämd)
↑ ScienceDirect - Journal of Algorithms: Analysen av Heapsort . Hämtad 30 september 2017. Arkiverad från originalet 4 juni 2012. (obestämd)

Litteratur

Levitin A.V. Kapitel 6. Transformationsmetod: Heaps and Heapsort // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 275-284. — 576 sid. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 6. Heapsort // Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - S. 182-188. — ISBN 5-8459-0857-4 .

Länkar

Heap sort - en detaljerad beskrivning med illustrationer och ett exempel på implementering i C ++. Härledningen av uppskattningar av algoritmens hastighet och mätningen av körtiden på ett riktigt beräkningssystem ges.
Sortering med hjälp av en hög (högsortering) - en begriplig beskrivning med illustrationer och en exempelimplementering i Pascal.
Dynamisk visualisering 7 sorteringsalgoritmer med öppen källkod Arkiverad 20 september 2017 på Wayback Machine

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam