Smidig sortering

Smoothsort är en  urvalssorteringsalgoritm , en sorts heapsortering , utvecklad av E. Dijkstra 1981. Liksom heapsort har den en komplexitet i värsta fall av O ( n log  n ) . Fördelen med smoothsort är att dess komplexitet närmar sig O( n ) om inmatningen är delvis sorterad, medan heapsort alltid har samma komplexitet, oavsett tillståndet för inmatningen.

Allmän introduktion

Precis som med heapsort ackumuleras en hög med data i en array, som sedan sorteras genom att kontinuerligt ta bort det maximala från högen. Till skillnad från heapsort använder den inte en binär hög , utan en speciell som erhålls med hjälp av Leonardo-tal . En hög består av en sekvens av högar, vars storlek är lika med ett av Leonardo-talen, och rötterna lagras i stigande ordning. Fördelen med sådana speciella högar framför binära är att om sekvensen sorteras kommer det att ta O( n ) tid att skapa och förstöra den, vilket är snabbare. Att dela upp indata i högar är enkelt: noderna längst till vänster i arrayen kommer att utgöra den största högen, och de återstående kommer att delas upp på liknande sätt.

• En array av valfri längd kan också delas upp i bitar av storleken L( x ) .
• Det bör inte finnas två högar av samma storlek, för i det här fallet kommer sekvensen att bli strikt minskande i storlek.
• Det får inte finnas två högar som har storlekar lika med två på varandra följande Leonardo-nummer, förutom en array med längden 2.

Dessa påståenden kan bevisas.

Varje hög med storlek L( x ) består, från vänster till höger, av en underhög av storlek L( x − 1 ) , en underhög av storlek L( x − 2 ) och en rot, utom högar av storlek L(1 ). ) och L(0) , som endast består av roten. För varje hög gäller följande egenskap: värdet på roten måste vara minst lika stort som värdena på rötterna för dess underhögar (och, som ett resultat, inte mindre än värdena för alla noder av dess barnhögar). För en sekvens av högar gäller i sin tur följande egenskap: värdet på roten av varje hög måste vara minst lika stort som värdet på roten på högen till vänster. Konsekvensen av detta är att noden längst till höger i sekvensen kommer att ha det högsta värdet, och viktigare är att en delvis sorterad array inte behöver omarrangeras för att bli en riktig heapsekvens. Detta är källan till algoritmens anpassningsförmåga. Algoritmen är enkel. Först delas den osorterade matrisen i en hög med ett element och en osorterad del. En hög med ett element är uppenbarligen en riktig sekvens av högar. Sekvensen börjar växa genom att lägga till ett element från höger i taget (vid behov byts elementen så att heap-egenskapen och sekvensegenskapen håller) tills den når storleken på den ursprungliga arrayen. Och från och med nu kommer elementet längst till höger i sekvensen av högar att vara det största för någon hög, och kommer därför att vara i den korrekta, slutliga positionen. Högsekvensen reduceras sedan till en hög med ett element genom att ta bort noden längst till höger och flytta om elementen för att återställa tillståndet för högen. Så snart det finns en hög med ett element kvar kommer arrayen att sorteras.

Operationer

Två operationer krävs: att öka högsekvensen genom att lägga till ett element till höger, och minska den genom att ta bort elementet längst till höger (roten av den sista högen), samtidigt som tillståndet för högen och sekvensen av högar bevaras.

Öka sekvensen av högar genom att lägga till ett element till höger

• Om de två sista högarna är L( x + 1 ) och L( x ) (två på varandra följande Leonardo-tal), blir det nya elementet roten till den större högen, L( x + 2 ) . För det är heap-egenskapen valfri.
• Om storleken på de två sista högarna inte är lika med två på varandra följande Leonardo-tal, bildar det nya elementet en ny hög med storlek 1. Denna storlek antas vara L(1) , om inte högen längst till höger redan har storlek L(1) , i vilket fall storleken på den nya ettelementhögen antas vara lika med L(0) .

Därefter måste egenskaperna för högen och sekvensen av högar återställas, vilket vanligtvis uppnås med en variant av insättningssort :

1. Högen längst till höger (senast bildad) anses vara den "nuvarande" högen.
2. Så länge det finns en hög till vänster och värdet av dess rot är större än värdet på den nuvarande roten och båda rötterna av barnhögarna:
   • Den nya roten och heaproten till vänster byts ut (vilket inte kommer att bryta egenskapen för den aktuella högen). Denna hög blir den nuvarande högen.
3. En "siktning" utförs så att högegenskapen är uppfylld:
   • Så länge storleken på den aktuella högen är större än 1 och värdet på roten av någon av de underordnade högarna är större än värdet på roten av den aktuella högen:
     • Den största roten av barnhögen och den nuvarande roten byts om. Barnhögen blir den nuvarande högen.

Sållningsoperationen förenklas avsevärt genom att använda Leonardo-nummer, eftersom varje hög antingen kommer att ha en singel eller två barn. Det finns ingen anledning att oroa sig för att missa en av barnhögarna.