Sorteringsalgoritmer jämförda

Det finns ingen enskild snabbaste sorteringsalgoritm. Vissa är enkla men långsamma, vissa är snabba på slumpade data men snubblar på sorterade data, och vissa är inte jämförelsebaserade alls. Låter du alla åtta tävla på samma lista ser du skillnaderna direkt.

Åtta banor med staplar, en per sorteringsalgoritm, där vissa redan är sorterade och gröna medan andra fortfarande är osorterade
Åtta banor med staplar, en per sorteringsalgoritm, där vissa redan är sorterade och gröna medan andra fortfarande är osorterade

Tre familjer

Bubbelsortering, urvalssortering och insättningssortering är de enkla sorteringarna. De jämför och byter värden som ligger nära varandra och behöver tid proportionell mot n² på en slumpad lista. Mergesort, quicksort och heapsort delar upp arbetet smart och behöver tid proportionell mot n log n, vilket är det bästa en sortering kan klara när den bara får fråga vilket av två värden som är störst. Radixsortering och räknesortering hoppar helt över den frågan: de använder själva siffrorna eller värdena, vilket bara fungerar för nycklar som små heltal.

Att mäta arbetet

Sorteringsracet räknar en operation för varje jämförelse, varje läst siffra eller värde och varje byte eller flytt. Med 40 slumpade värden blir det ungefär 120 för räknesortering, 240 för radixsortering, 260 för quicksort, 380 för mergesort, 490 för heapsort, ungefär 820 var för urvalssortering och insättningssortering och över 1 100 för bubbelsortering. Riktiga datorer bryr sig också om minnet: quicksort är i praktiken oftast snabbare än räkningen antyder, och heapsort långsammare, på grund av hur de rör sig genom listan.

Indata spelar roll

På en nästan sorterad lista behöver insättningssortering bara ungefär 50 operationer för 40 värden och bubbelsortering ungefär 90, eftersom varje värde ligger nära sin plats. På en omvänd lista behöver samma två 1 560, deras värsta fall. Urvalssortering, heapsort, mergesort, radixsortering och räknesortering bryr sig knappt om ordningen. Quicksort med median av tre klarar sorterade och omvända listor bra, men med en naiv pivot är en sorterad lista dess värsta fall. Få unika värden gör quicksort långsammare, eftersom lika värden alla hamnar på samma sida.

Minne och stabilitet

Bubbelsortering, urvalssortering, insättningssortering, quicksort och heapsort sorterar på plats, med lite eller inget extra minne. Mergesort, radixsortering och räknesortering behöver en buffert lika lång som listan. En stabil sortering behåller lika värden i sin ursprungliga ordning: bubbelsortering, insättningssortering, mergesort, radixsortering och räknesortering är stabila, medan urvalssortering, quicksort och heapsort inte är det. Stabilitet spelar roll när du sorterar poster efter ett fält i taget.

Vilken ska du använda?

I praktiken använder du den sortering som är inbyggd i ditt programmeringsspråk: oftast Timsort, en mergesort som använder insättningssortering för korta delar och är snabb på delvis sorterade data, eller introsort, en quicksort som faller tillbaka på heapsort och använder insättningssortering för små delar. För många små heltalsnycklar kan räknesortering eller radixsortering slå båda. Bubbelsortering och urvalssortering är mest verktyg för undervisning.

Utforska själv

Öppna sorteringsracet och tryck på Spela. Varje bana är en sortering på samma lista; talet till höger räknar dess operationer, och en bana blir grön när den är klar. Prova en nästan sorterad lista, en omvänd lista och få unika värden, och se målgångsordningen ändras. Varje sortering har också en egen app där du kan stega igenom den i detalj.

Ofta ställda frågor

Vilken är den snabbaste sorteringsalgoritmen?

För allmänna data är quicksort och mergesort (och hybrider byggda på dem, som introsort och Timsort) snabbast i genomsnitt, med n log n. För små heltalsnycklar är räknesortering och radixsortering ännu snabbare. För korta eller nästan sorterade listor vinner insättningssortering.

Varför kan ingen jämförelsebaserad sortering slå n log n?

En lista med n värden kan stå i n! ordningar, och varje jämförelse har två utfall, så det behövs minst log₂(n!) jämförelser för att skilja dem alla åt i värsta fall. Det är ungefär n log₂ n. Radixsortering och räknesortering undviker den gränsen eftersom de inte jämför.

Vilka sorteringsalgoritmer är stabila?

Bubbelsortering, insättningssortering, mergesort, radixsortering och räknesortering är stabila i sina vanliga former. Urvalssortering, quicksort och heapsort är det inte, eftersom de flyttar värden långa sträckor.

Vilka sorteringar behöver extra minne?

Mergesort, radixsortering och räknesortering behöver en buffert ungefär lika lång som listan. Bubbelsortering, urvalssortering, insättningssortering och heapsort behöver nästan inget, och quicksort bara lite för sin rekursion.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Starta sorteringsracet