Sortering

Här finns två sidor med mycket bra illustrationer av olika sorteringsalgoritmer:
http://cs.smith.edu/~thiebaut/java/sort/demo.html
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html .

Sortering är ett vanligt förekommande problem inom datalogin. Dels finns det en enorm massa applikationer som presenterar sorterat data för användaren, tex adresslistor, innehållsförteckningar, kalendrar. Dels finns det många andra tillämpningar av sortering. Antag till exempel att vi ska avgöra om en sekvens innehåller några dubletter. En enkel lösning är då att jämför alla element med alla andra element. Detta ger två nästlade loopar, dvs O(T(n)) = n². Antag istället att vi först sorterar sekvensen. Dubletter kommer då att ligga bredvid varandra och vi kan hitta dem genom att helt enkelt gå igenom hela sekvensen, vilket ger O(T(n)) = n. Går det att sortera snabbare än n² blir denna lösning bättre än den föregående.

Eftersom sortering är så vanligt finns det en mängd välkända sorteringsalgoritmer med olika egenskaper. Vi ska titta både på enklare, långsamma och på mer komplicerade men snabbare.

Det vanligaste är att ett antal poster ska sorteras efter en viss nyckel (eller efter flera nycklar) som endast utgör en del av hela posten. I exemplen här består posterna för enkelhets skull endast av en nyckel (som är en int). De enda algoritmerna där nycklarnas typ påverkar sorteringen är radixsort och bucketsort, hur står i de stycken där dessa algoritmer behandlas.

Enkla algoritmer med O(T(n)) = n²

Först ska vi titta på två enkla algoritmer som båda bygger på nästlade loopar, dvs varje nyckel jämförs med de andra nycklarna.

Bubble Sort

Detta är kanske den enklaste (och långsammaste) av alla sorteringsalgoritmer. Vi går helt enkelt igenom sekvensen från början till slut och jämför alla element parvis. Om elementet med lägst index är störst byter vi plats på elementen. På så sätt kommer det största elementet att hamna sist. Sedan gör vi om samma procedur tills alla element har jämförts med alla andra.

Denna algoritm kan enkelt förbättras eftersom det element som hamnar sist efter det första varvet i den yttre loopen är det största av alla element, vi behöver alltså inte jämföra med det på nästa varv. Vi behöver över huvud taget aldrig jämföra med de element som redan är sorterade. Här kommer ett sådant program, BubbleSort.c . Denna algoritm resulterar i ungefär n(n-1)/2 varv i den inre loopen. Detta innebär att O(T(n)) = n². Hur lång tid det faktiskt tar att sortera sekvensen beror på hur många av varven som leder till att två element byter plats. Worst case är att sekvensen är sorterad i omvänd ordning, då kommer element att byta plats på varje varv. Genomsnittet är att vartannat varv leder till ett byte, vilket ger n(n-1)/2/2 = n(n-1)/4 byten.

För jämförelse med övriga algoritmer anges att exekveringen av BubbleSort.c på min dator tog 5s när 10000 element sorterades och 20s när 20000 element sorterades.

En ytterligare förbättring vore att inte flytta efter varje jämförelse. Det skulle räcka att gå igenom hela sekvensen, identifiera det största elementet och sedan placera det sist.

Instickssortering

Se figur 12.2 på sid 185 i kompendiet. Översta raden är den sekvens som ska sorteras. Vi börjar med att jämföra det andra elementet (5) med alla element till vänster om det. Vi stoppar in det på rätt plats, dvs före alla större element. Nu finns det inga större element till vänster om 5:an så den blir kvar i position två. Därefter betraktar vi elementen i tur och ordning från vänster till höger, jämför med alla element till vänster och stoppar in det före alla större element. Den första gången det blir en förändring är när vi undersöker det fjärde elementet (2). Alla element till vänster om det är större varför det hamnar först, detta har skett på rad två i figuren. När vi har undersökt alla element är sekvensen sorterad. Här kommer en implementation av denna algoritm, InsertionSort.c .

Analysen av exekveringshastigheten är identisk med den för bubble sort. För jämförelse med övriga algoritmer anges att exekveringen av InsertionSort.c på min dator tog 2s när 10000 element sorterades och 7s när 20000 element sorterades.

Snabbare (men mer komplicerade) algoritmer

Ovanstående två var exempel på algoritmer som var relativt enkla att implementera men tyvärr ganska långsamma. Nu ska vi titta på några snabbare algoritmer som desvärre också är krångligare.

Mergesort

Vi gick igenom denna algoritm i avsnittet om söndra och härska (och tog upp en möjlig förbättring i avsnittet om dynamisk programmering ). I mycket korta drag sorteras sekvenser med n element rekursivt på förljande sätt:

Om n <= 2 sorteras elementen direkt.
Om n > 2 utförs följande tre moment.

Sortera sekvensens vänstra halva genom ett rekursivt anrop av funktionen.
Sortera sekvensens högra halva genom ett rekursivt anrop av funktionen.
Sortera ihop de nu sorterade halvorna till en sorterad sekvens.

Det ständiga uppdelandet i halvor leder till att stora mängder data kopieras. Sorteringen blir snabbare om vi allokerar plats för nya sekvenser vid varje rekursivt anrop eftersom vi då inte behöver flytta andra element än de som just sorteras. Det gör dock funktionen väsentligt mer minneskrävande. Eftersom det är en laborationsuppgift att implementera merge sort blir det inget exempelprogram här.

Som visades i avsnittet om söndra och härska är O(T(n)) = nlog(n). Nackdelen med denna algoritm är att relativt stora mängder data flyttas. Försöker vi minimera datakopieringen blir algoritmen i stället mer minneskrävande.

Shellsort

Detta var den första sorteringsalgoritmen (uppfunnen 1959) som var markant snabbare än instickssortering. Det är inte den snabbaste algoritmen men den har bra prestanda och är förbluffande enkel att implementera (bara ett par rader kod mer än instickssortering).

Grunden är exakt densamma som för instickssortering (dvs flytta element före alla större element) men här undviks de stora mängderna datakopiering genom att först jämföra och sortera element långt från varandra och sedan element allt närmre varandra tills vi till slut utför en vanlig instickssortering. På så sätt kommer små element långt bak i sekvensen framåt i stora hopp i de första sorteringarna, se figur 12.4 på sid 187.

När shellsort ska implementeras måste vi bestämma en följd h₁, h₂, ..., h_t. Först ska element med avståndet (gap) h_t mellan sig sorteras. Därefter element på avståndet h_t-1 osv ner till element på avståndet h₁. För att sekvensen ska bli fullständigt sorterad måste h₁ vara 1, dvs sista sorteringen är en vanlig instickssortering. Det visar sig att valet av följden i hög grad påverkar exekveringshastigheten. Många olika följder har föreslagits, för en del går det att beräkna W(n) och A(n), för andra finns det bara uppmätta värden. En enkel följd som ger bra resultat är att välja h_t = n/2 och därefter successivt dividera h_k med 2.2 till h₁ = 1 nås. Denna följd tycks innebära att O(A(n)) < n^5/4, kanske så låg som n^7/6. Detta är uppmätta värden, ingen har lyckats beräkna A(n) för denna följd. Här kommer en implementation av shellsort med denna följd, ShellSort.c . För jämförelse med övriga algoritmer anges att exekveringen av ShellSort.c på min dator tog 3s när 1000000 element sorterades.

Heapsort

Denna algoritm bygger på datastrukturen binär heap. En heap är ett träd där alla noder har större (eller alla noder har mindre) nyckel än sin förälder. I en binär heap är trädet ett komplett binärt träd, dvs alla noder finns på nivå n eller n-1 och alla noder på nivå n finns i de vänstraste positionerna, se figur 12.5 och 12.6 på sid 190. Efter som ett komplett binärt träd har en väldigt förutsägbar form går det bra att lagra det i en array. Elementet på index 0 i arrayen är då roten. Rotens barn finns på index 1 och 2. Barnen till noden på index 1 finns på index 3 och 4 osv. Generellt har noden på index i sina barn på index 2i + 1 och 2i + 2 (om första index är 0).

Heapsort går ut på att först stuva om sekvensen så att den bildar en binär heap. I ett sådant träd finns den största (eller minsta) nyckeln alltid i roten. Denna omstuvning sker genom att vi först betraktar den sista (i arrayen) föräldern och dess barn och gör en binär heap av dem. Därefter gör vi en binär heap av den näst sista föräldern och dess barn osv ända tills roten och dess barn (dvs alla noder) utgör en binär heap. Därefter plockas roten bort ur heapen som stuvas om så att den på nytt utgör en binär heap, roten ur den nya heapen plockas ut osv tills alla element är borta ur heapen. Elementen har då plockats ut i sorterad ordning. Hela detta förlopp illustreras av figur 12.7 på sid 191.

Detta är i teorin enkelt men leder till relativt komplicerad kod. Här kommer en implementation, HeapSort.c . Även i detta fall behövde min dator 3s för att sortera 1000000 tal. För heapsort gäller (helt utan bevis) att O(W(n)) = O(A(n)) = nlog(n). Med en lite noggrannare mätning blir heapsort kanske något snabbare än shellsort men till priset av krångligare kod.

Quicksort

Quicksort är den snabbast kända sorteringsalgoritmen som är praktisk att använda utan att ställa krav på sekvensen som ska sorteras. Den bygger på följande rekursiva algoritm:

Gör ingenting om antalet element i sekvensen är 0 eller 1.
Välj ett godtyckligt element (kallas pivotelement).
Flytta alla element mindre än pivotelementet till vänster om det.
Flytta alla element större än pivotelementet till höger om det.
Sortera rekursivt delsekvensen till vänster om pivotelementet.
Sortera rekursivt delsekvensen till höger om pivotelementet.

Observera att eftersom vi använder rekursion blir det inga loopar över hela sekvensen. Anledningen till att quicksort är snabbare än mergesort (som är en snarlik algoritm) är att quicksort inte kräver att elementen kopieras mellan olika sekvenser.Best case blir när pivotelementet hela tiden ligger mitterst i sekvensen. Då blir, enligt samma resonemang som för mergesort, O(B(n)) = nlog(n). Utan att presentera beviset är även O(A(n)) = nlog(n). Worst case är när pivotelementet alltid ligger i sekvensens ena ända. Vid varje rekursivt anrop kommer sekvensen då att innehålla endast ett element mindre (pivotelementet från föregående anrop). Detta innebär att funktionen exekveras n gångar och att i genomsnitt n/2 element behandlas varje gång. Detta antyder att O(W(n)) skulle vara O(n * n/2) = O(n²). Ett mer formellt bevis visar att så är fallet.

Uppenbarligen har valet av pivotelement stor betydelse för algoritmens prestanda. Andra faktorer som har stor betydelse är hur uppdelningen i större och mindre element utförs och hur element lika stora som pivotelementet behandlas. Dessa är bra metoder:

Välj som pivotelementet det som har medianvärdet av sekvensens första, mittersta och sista element. Detta ger snabbt ett element som är tillräckligt nära hela sekvensens medianvärde. Placera det minsta av dessa tre element först, pivotelementet mitterst och det största sist i sekvensen. Detta underlättar arbetet i nästa punkt (och måste ändå göras).
Partitionera genom att först byta plats på pivotelementet och elementet på näst högst index. Detta för att vi inte vet på vilket index pivotelementet till slut hamnar. Nu är det ur vägen tills vi vet det.

Punkten ovan innebär att vi byter plats på element som är lika stora som pivotelementet. Anledningen till det är att vi vill få i och j att mötas så nära sekvensens mitt som möjligt för att dela upp sekvensen i så jämnstora delar som möjligt och därmed minska antalet rekursioner.

Observera att quicksortalgoritmen som illustreras i figuren påsid 196 inte följer ovanstående strategi, det gör däremot programmet QuickSort.c . Det innehåller ytterligare en förbättring, när sekvensen blir kortare än tio element upphör rekursionen och i stället utförs instickssortering på de sista tio elementen. Detta på grund av att rekursionen tar längre tid än vad vi vinner på den bättre algoritmen (quicksort) för så små sekvenser. Detta program behöver bara 1s för att sortera 1000000 tal på min dator.

Sorteringsalgoritmer som bygger på jämförelse kan inte ha O(T(n)) < nlog(n)

Antag att en godtycklig sekvens med n element ska sorteras. Vi kan betrakta antalet möjliga indata till sorteringsrutinen som alla permutationer av talen 1, 2, 3 ... n eftersom elementens faktsiska värde inte påverkar sorteringen, bara hur de förhåller sig till varandra. Det finns n! permutationer av n element.

Låt P_i vara antalet permutationer som fortfarande är möjliga efter att algoritmen har utfört i jämförelser. Låt F vara antalet jämförelser som krävs för att sekvensen ska vara sorterad. Vi vet då att P₀ = n! eftersom alla möjliga permutationer kan vara indata till algoritmen. Vidare måste P_F vara 1 eftersom slutresultatet har ett förutbestämt utseende, nämligen en fullständigt sorterad sekvens.

Vid varje jämförelse delas antalet möjliga permutationer in i två grupper: de som inte längre är möjliga och de som fortfarande är möjliga. De senare är de som ska behandlas vid nästa jämförelse. Den största av dessa två grupper innehåller minst hälften av alla permutationer. I värsta fall (worst case) är det alltid gruppen med permutaioner som fortfarande är möjliga. Det kan förstås vara ännu sämre, att till exempel inga permutationer går att utesluta, men i "bästa värsta fall" kan hälften av permutationerna uteslutas vid varje jämförelse.

Om vi ska gå från n! till 1 permutation och halvera antalet vid varje jämförelse krävs det log₂(n!) jämförelser. log₂(n!) är ungefär nlog₂(n) - 1.44n. Alltså är O(W(n)) = nlog(n). Det går att, på likartat sätt, visa att även O(A(n)) = nlog(n).

Sorteringsalgoritmer som inte bygger på jämförelse med O(T(n)) = n

Nu ska vi titta på en sorteringsalgoritm som inte bygger på jämförelse och som därför kan ha (och har) en komplexitetsfunktion som är O(n). Algoritmer av denna typ kan vara extremt snabba men är tyvärr inte generella, dvs de ställer krav på en sekvens för att kunna sortera den.

Countingsort (Detta är inte Bucketsort som tidigare felaktigt angivits)

Countingsort kräver att alla möjliga värden av de element som ska sorteras är kända. Algoritmen är lika enkel som genial. Skapa en array som har alla möjliga elementvärden som index och initiera alla celler i arrayen till noll. Läs sedan igenom sekvensen som ska sorteras, om ett element har värdet x ökas cellen med index x med ett. Loopa sedan igenom hela arrayen och skriv ut array[index] element med värdet index. Här kommer ett program som gör detta, Countingsort.c . Med min primitiva tidmätning går det inte att uppskatta tiden, det tar 0s att sortera 1000000 tal.

B(n) = A(n) = W(n) = O(2n + (n_max- n_min)), där n_max och n_min är det största respektive minsta värdet elementen kan anta. Vi har alltså en sorteringsrutin med linjär komplexitetsfunktion!! Problemet är dels att vi måste veta alla möjliga värden hos de element som ska sorteras, dels att vi behöver allokera minne för n_max element. I och för sig behöver arrayen som räknar elementen inte nödvändigtvis vara en array av int, vet vi att det inte finns mer än 255 av varje element räcker det med en array av bytes osv. Dock krävs det att n_max är hanterbart litet, vilket inte är fallet om det är till exempel strängar som ska sorteras. Det krävs också att n_max-n_min inte är alltför stort jämfört med n.

Ytterligare ett problem är om det finns en sekundär nyckel, dvs om ordningen av lika stora element har betydelse. I så fall går det inte att bara skriva ut array[index] element med värdet index. Det blir i stället nödvändigt att hitta elementen i sekvensen och sortera dem med avseende på deras sekundära nyckel.

Att välja en sorteringsalgoritm

Om det är helt säkert att n_max- n_min aldrig är för stort jämfört med n och att vi har råd med det extra minne som krävs är countingsort bäst av algoritmerna ovan. Om inte är instickssortering sannolikt bäst om n är litet eller om indatat redan är närapå sorterat. Den är enkel att konstruera och kräver inget extra minne. Behövs en snabbare algoritm kan shellsort vara bra om dess prestanda räcker eftersom den är så enkel att konstruera. Behövs en ännu snabbare algoritm är quicksort det rätta valet. Varken shellsort eller quicksort kräver något extra minne.

Extern sortering

Hittils har vi hela tiden förutsett att alla poster får plats i primärminnet samtidigt. Om så inte är fallet ändras prestanda drastiskt. Till exempel blir quicksort långsam eftersom den i varje rekursion behandlar poster fördelade över hela sekvensen, vilket innebär att de om och om igen måste läsas in från något externt lagringsmedia (till exempel hårddisk eller band). Faktum är att beräkningarna av O(T(n)) blir helt meningslösa eftersom de förutsätter att alla operationer tar lika lång tid. Det är inte fallet nu eftersom det tar mycket längre tid att komma åt en post som inte finns i primärminnet.

En lösning på detta problem är att skapa indexfiler som bara innehåller nyckel och postnummer (mer om det i nästa avsnitt). Kanske kan dessa läsas in i primärminnet och sorteras. Sedan kan vi hitta posterna i sorterad ordning med hjälp av postnumren i indexfilen. I värsta fall går inte heller detta, kanske på grund av att inte ens indexfilen får plats i primärminnet. I så fall är det viktigaste att begränsa antalet accesser av det externa mediat. För detta krävs att så få poster som möjligt accessas i varje rekursion/iteration och att de som accessas ligger nära varandra.

I detta fall är mergesort den överlägset bästa av algoritmerna ovan. Den delar först upp sekvensen i små delsekvenser utan att accessa posterna. Därefter sorteras delsekvenserna var för sig. Det innebär att en delsekvens kan läsas in, sorteras och skrivas ut på det externa mediat igen. Därefter läses nästa delsekvens in, sorteras, skrivs ut osv. När delsekvenserna som ska samsorteras blir så stora att de inte får plats i primärminnet räcker det ändå att läsa in posterna en gång eftersom vi bara jämför de första elementen i varje delsekvens.