Smoothsort

Smoothsort

Smoothsort som arbetar på en array som för det mesta är i sin ordning. Staplarna över toppen visar trädstrukturen.
Klass	Sorteringsalgoritm
Datastruktur	Array
Prestanda i värsta fall	O ( n log n )
Bästa möjliga prestanda	O ( n )
Genomsnittlig prestanda	O ( n log n )
Värsta tänkbara utrymmeskomplexitet	O ( n ) totalt, O (1) hjälpmedel

Inom datavetenskap är smoothsort en jämförelsebaserad sorteringsalgoritm . En variant av heapsort , den uppfanns och publicerades av Edsger Dijkstra 1981. Liksom heapsort är smoothsort en in-place-algoritm med en övre gräns för O ( n log n ) , men det är inte en stabil sort . Fördelen med smoothsort är att den kommer närmare O ( n ) tid om inmatningen redan är sorterad i någon grad , medan heapsort genomsnitt O ( n log n ) oavsett det initiala sorterade tillståndet.

Översikt

Liksom heapsort organiserar smoothsort inmatningen i en prioritetskö och extraherar sedan maxvärdet upprepade gånger. Liksom heapsort är prioritetskön en implicit heap-datastruktur (ett heap -ordnat implicit binärt träd ), som upptar ett prefix för arrayen. Varje extraktion krymper prefixet och lägger till det extraherade elementet till ett växande sorterat suffix. När prefixet har krympt till ingenting är arrayen helt sorterad.

Heapsort mappar det binära trädet till arrayen med hjälp av en uppifrån och ned bredd-först genomgång av trädet; arrayen börjar med trädets rot, sedan dess två barn, sedan fyra barnbarn och så vidare. Varje element har ett väldefinierat djup under trädets rot, och varje element utom roten har sin förälder tidigare i arrayen. Dess höjd över löven beror dock på storleken på arrayen. Detta har nackdelen att varje element måste flyttas som en del av sorteringsprocessen: det måste passera genom roten innan det flyttas till sin slutliga plats.

Smoothsort använder en annan mappning, en nedifrån och upp djup-först post-order genomgång . Ett vänsterbarn följs av underträdet som är rotat på sitt syskon, och ett högerbarn följs av sin förälder. Varje element har en väldefinierad höjd ovanför bladen, och varje element som inte är löv har sina barn tidigare i arrayen. Dess djup under roten beror dock på storleken på arrayen. Algoritmen är organiserad så att roten är i slutet av högen, och i det ögonblick som ett element extraheras från högen är det redan på sin slutliga plats och behöver inte flyttas. Dessutom är en sorterad array redan en giltig hög, och många sorterade intervall är giltiga högordnade underträd.

Mer formellt är varje position i roten till ett unikt underträd, vars noder upptar ett sammanhängande intervall som slutar på i . Ett initialt prefix för arrayen (inklusive hela arrayen) kan vara ett sådant intervall som motsvarar ett underträd, men sönderdelas i allmänhet som en förening av ett antal på varandra följande sådana underträdsintervall, som Dijkstra kallar "sträckningar". Varje underträd utan en förälder (dvs. rotat på en position vars förälder ligger bortom prefixet i fråga) ger en sträcka i nedbrytningen av det intervallet, vilken nedbrytning därför är unik. När en ny nod läggs till prefixet uppstår ett av två fall: antingen är positionen ett löv och lägger till en sträcka med längden 1 till nedbrytningen, eller så kombineras den med de två sista sträckorna och blir föräldern till deras respektive rötter, sålunda ersätter de två sträckorna med en ny sträcka som innehåller deras förening plus den nya (rot)positionen.

Dijkstra noterade att den självklara regeln skulle vara att kombinera sträckor om och endast om de har samma storlek, i vilket fall alla underträd skulle vara perfekta binära träd med storleken 2 ^k −1 . Han valde dock en annan regel, som ger fler möjliga trädstorlekar. Detta har samma asymptotiska effektivitet , men får en liten konstant faktor i effektivitet genom att kräva färre sträckor för att täcka varje intervall.

Regeln som Dijkstra använder är att de två sista sträckorna kombineras om och endast om deras storlekar är på varandra följande Leonardo-tal L ( i +1) och L ( i ) (i den ordningen), vilka tal är rekursivt definierade, på ett sätt som är mycket lika till Fibonacci-talen , som:

• L (0) = L (1) = 1
• L ( k +2) = L ( k +1) + L ( k ) + 1

Som en konsekvens är storleken på ett underträd ett Leonardo-nummer. Sekvensen av sträckstorlekar som bryter ned de första n positionerna, för vilket n som helst , kan hittas på ett girigt sätt: den första storleken är det största Leonardo-talet som inte överstiger n , och resten (om någon) bryts ned rekursivt. Storleken på sträckorna minskar, strikt så förutom möjligen för två slutliga storlekar 1, och man undviker successiva Leonardo-nummer förutom möjligen för de två sista storlekarna.

Förutom att varje sträcka är ett högordnat träd, hålls trädens rötter i sorterad ordning. Detta lägger effektivt till ett tredje barn (som Dijkstra kallar en "styvson") till varje rot som länkar den till den föregående roten. Detta kombinerar alla träden till en global hög. med det globala maximumet i slutet.

Även om platsen för varje nods styvson är fast, existerar länken bara för trädrötter, vilket innebär att länkar tas bort när träd slås samman. Detta skiljer sig från vanliga barn, som är sammanlänkade så länge föräldern finns.

I den första (högväxande) fasen av sorteringen omorganiseras en allt större initial del av arrayen så att underträdet för var och en av dess sträckor är en max-hög: ingången vid valfri icke-bladsposition är minst lika stor som posterna på de positioner som är dess barn. Dessutom är alla rötter minst lika stora som deras styvsöner.

I den andra (högkrympande) fasen frigörs den maximala noden från änden av arrayen (utan att behöva flytta den) och heapinvarianterna återupprättas bland dess barn. (Särskilt bland de nyskapade styvsönerna.)

Praktisk implementering behöver ofta beräkna Leonardo-tal L ( k ) . Dijkstra tillhandahåller smart kod som använder ett fast antal heltalsvariabler för att effektivt beräkna de värden som behövs vid den tidpunkt de behövs. Alternativt, om det finns en ändlig bunden N på storleken på arrayer som ska sorteras, kan en förberäknad tabell med Leonardo-tal lagras i O (log N ) utrymme.

Operationer

Medan de två faserna av sorteringsproceduren är motsatta varandra när det gäller utvecklingen av sekvens-av-högstrukturen, implementeras de med en kärnprimitiv, motsvarande "sålla ner" operationen i en binär max- högen.

Siktar ner

Kärnsållningsoperationen (som Dijkstra kallar " trinkle ") återställer heapinvarianten när den möjligen bara brytes vid rotnoden. Om rotnoden är mindre än någon av dess underordnade, byts den ut mot dess största underordnade och processen upprepas med rotnoden i dess nya underträd.

Skillnaden mellan smoothsort och en binär max-heap är att roten av varje sträcka måste ordnas med avseende på en tredje "styvson": roten av föregående sträcka. Så sållningsproceduren börjar med en serie fyrvägsjämförelser (rotnoden och tre barn) tills styvsonen inte är det maximala elementet, sedan en serie trevägsjämförelser (roten plus två barn) tills roten noden hittar sitt slutliga hem och invarianterna återupprättas.

Varje träd är ett fullständigt binärt träd : varje nod har två barn eller ingen. Det finns inget behov av att ta itu med det speciella fallet med ett barn som inträffar i en standard implicit binär hög . (Men specialfallet med styvsonslänkar kompenserar mer än för denna besparing.)

Eftersom det finns O (log n ) sträckor, som var och en är ett träd med djup O (log n ) , är tiden för att utföra varje sållningsoperation begränsad av O (log n ) .

Öka högregionen genom att införliva ett element till höger

När ett ytterligare element övervägs att införlivas i sekvensen av sträckor (lista över osammanhängande högstrukturer) bildar det antingen en ny sträcka med ett element, eller så kombinerar det de två sträckorna längst till höger genom att bli förälder till båda deras rötter och bilda en ny sträcka som ersätter de två i sekvensen. Vilken av de två som händer beror bara på storleken på de sträckor som för närvarande finns (och i slutändan bara på indexet för det tillsatta elementet); Dijkstra stipulerade att sträckor kombineras om och endast om deras storlekar är L ( k +1) och L ( k ) för vissa k , dvs. på varandra följande Leonardo-tal; den nya sträckan kommer att ha storlek L ( k +2) .

I båda fallen måste det nya elementet siktas ner till sin rätta plats i högstrukturen. Även om den nya noden är en sträcka med ett element, måste den fortfarande sorteras i förhållande till den föregående sträckans rot.

Optimering

Dijkstras algoritm sparar arbete genom att observera att full heap-invariant krävs i slutet av odlingsfasen, men det krävs inte vid varje mellansteg. Speciellt är kravet att ett element är större än dess styvson endast viktigt för de element som är de slutliga trädrötterna.

Därför, när ett element läggs till, beräkna positionen för dess framtida överordnade. Om detta ligger inom intervallet för återstående värden som ska sorteras, agera som om det inte finns någon styvson och sålla bara ner inom det aktuella trädet.

Krympa högområdet genom att separera elementet längst till höger från det

Under denna fas går formen av sekvensen av sträckor genom förändringarna av tillväxtfasen i omvänd riktning. Inget arbete behövs alls när man separerar en lövnod, men för en icke-lövnod blir dess två barn rötter till nya sträckor och måste flyttas till sin rätta plats i sekvensen av rötter av sträckningar. Detta kan erhållas genom att använda sålla två gånger: först för det vänstra barnet och sedan för det högra barnet (vars styvson var det vänstra barnet).

Eftersom hälften av alla noder i ett helt binärt träd är löv, utför detta i genomsnitt en sållningsoperation per nod.

Optimering

Det är redan känt att de nyligen exponerade rötterna är korrekt ordnade med avseende på deras normala barn; det är bara ordningen i förhållande till deras styvsöner som det är fråga om. Därför, samtidigt som högen krymper, kan det första steget att sikta ner förenklas till en enda jämförelse med styvsonen. Om ett byte inträffar måste de efterföljande stegen göra den fullständiga jämförelsen i fyra riktningar.

Analys

Smoothsort tar O ( n ) tid att bearbeta en försorterad array, O ( n log n ) i värsta fall, och uppnår nästan linjär prestanda på många nästan sorterade ingångar. Den hanterar dock inte alla nästan sorterade sekvenser optimalt. Genom att använda räkningen av inversioner som ett mått på osorterad (antalet par av index i och j med i < j och A [ i ] > A [ j ] ; för slumpvis sorterad indata är detta ungefär n ² /4 ), det finns möjliga ingångssekvenser med O ( n log n ) inversioner som gör att det tar Ω( n log n ) tid, medan andra adaptiva sorteringsalgoritmer kan lösa dessa fall i O ( n log n ) tid.

Slätsorteringsalgoritmen måste kunna hålla i minnet storleken på alla träden i Leonardo-högen. Eftersom de är sorterade efter ordning och alla order är distinkta, görs detta vanligtvis med hjälp av en bitvektor som indikerar vilka order som finns. Dessutom, eftersom den största ordern är högst O (log n ) , kan dessa bitar kodas i O (1) maskinord, under antagande av en transdikotom maskinmodell .

Observera att O (1) maskinord inte är samma sak som ett maskinord. En 32-bitars vektor skulle bara räcka för storlekar mindre än L (32) = 7049155 . En 64-bitars vektor duger för storlekar mindre än L (64) = 34335360355129 ≈ 2 ⁴⁵ . I allmänhet tar det 1/log ₂ ( φ ) ≈ 1,44 bitar av vektor per bit av storlek.

Poplar sort

En enklare algoritm inspirerad av smoothsort är poppelsortering . Uppkallad efter raderna av träd av minskande storlek som ofta ses i holländska poldrar , utför den färre jämförelser än smoothsort för indata som till största delen inte är sorterade, men som inte kan uppnå linjär tid för sorterade indata.

Den betydande förändring som görs av poppelsorteringen genom att de olika trädens rötter inte hålls i sorterad ordning; det finns inga "styvsonslänkar" som binder ihop dem till en enda hög. Istället, varje gång högen krymps i den andra fasen, genomsöks rötterna för att hitta den maximala ingången.

Eftersom det finns n krympande steg, som vart och ett måste söka O (log n ) trädrötter för maximalt, är den bästa körtiden för poppelsortering O ( n log n ) .

Författarna föreslår också att man använder perfekta binära träd snarare än Leonardo-träd för att ge ytterligare förenkling, men detta är en mindre betydande förändring.

Samma struktur har föreslagits som en allmänt prioriterad kö under namnet post-order heap , vilket uppnår O (1) amorterad insättningstid i en struktur som är enklare än en implicit binomial heap .

Ansökningar

Musl C - biblioteket använder smoothsort för sin implementering av qsort () .

externa länkar

• Kommenterad transkription av EWD796a, 16-aug-1981
• Detaljerad modern förklaring av Smoothsort
• wikibooks:Algorithm Implementation/Sorting/Smoothsort
• Beskrivning och exempelimplementering av Poplar heap
• Noshita, Kohei; Nakatani, Yoshinobu (april 1985). "På den kapslade högstrukturen i Smoothsort" . Matematiska grunder för datavetenskap och deras tillämpningar ( japanska : 数理解析研究所講究録 ) . 556 : 1–16.