Sorteringsalgoritmer sammenlignet

Der findes ikke én hurtigste sorteringsalgoritme. Nogle er enkle, men langsomme, nogle er hurtige på tilfældige data, men snubler over sorterede data, og nogle er slet ikke sammenligningsbaserede. Når alle otte kører om kap på den samme liste, ser du forskellene med det samme.

Otte baner med søjler, én pr. sorteringsalgoritme, hvor nogle allerede er sorteret og grønne, mens andre stadig er usorterede
Otte baner med søjler, én pr. sorteringsalgoritme, hvor nogle allerede er sorteret og grønne, mens andre stadig er usorterede

Tre familier

Boblesortering, udvælgelsessortering og indsættelsessortering er de enkle sorteringer. De sammenligner og bytter værdier, der står tæt på hinanden, og bruger tid proportional med n² på en tilfældig liste. Flettesortering, quicksort og heapsort deler arbejdet smart op og bruger tid proportional med n log n, hvilket er det bedste, en sortering kan opnå, når den kun må spørge, hvilken af to værdier der er størst. Radixsortering og tællesortering springer helt over det spørgsmål: de bruger selve cifrene eller værdierne, hvilket kun virker for nøgler som små hele tal.

Sådan måles arbejdet

Sorteringskapløbet tæller én operation for hver sammenligning, hvert aflæst ciffer eller hver aflæst værdi og hver ombytning eller flytning. Med 40 tilfældige værdier giver det omkring 120 for tællesortering, 240 for radixsortering, 260 for quicksort, 380 for flettesortering, 490 for heapsort, omkring 820 hver for udvælgelsessortering og indsættelsessortering og over 1.100 for boblesortering. Rigtige computere tager også hensyn til hukommelsen: quicksort er i praksis som regel hurtigere, end optællingen antyder, og heapsort langsommere, på grund af den måde, de bevæger sig gennem listen på.

Inputtet betyder noget

På en næsten sorteret liste kræver indsættelsessortering kun omkring 50 operationer for 40 værdier og boblesortering omkring 90, fordi hver værdi står tæt på sin plads. På en omvendt liste kræver de samme to 1.560, deres værste tilfælde. Udvælgelsessortering, heapsort, flettesortering, radixsortering og tællesortering er næsten ligeglade med rækkefølgen. Quicksort med medianen af tre klarer sorterede og omvendte lister godt, men med en naiv pivot er en sorteret liste dens værste tilfælde. Få unikke værdier gør quicksort langsommere, fordi ens værdier alle havner på den ene side.

Hukommelse og stabilitet

Boblesortering, udvælgelsessortering, indsættelsessortering, quicksort og heapsort arbejder in-place, med lidt eller ingen ekstra hukommelse. Flettesortering, radixsortering og tællesortering kræver en buffer, der er lige så lang som listen. En stabil sortering bevarer ens værdier i deres oprindelige rækkefølge: boblesortering, indsættelsessortering, flettesortering, radixsortering og tællesortering er stabile, mens udvælgelsessortering, quicksort og heapsort ikke er. Stabilitet betyder noget, når du sorterer poster efter ét felt efter et andet.

Hvilken skal du bruge?

I praksis bruger du den sortering, der er indbygget i dit programmeringssprog: som regel Timsort, en flettesortering, der bruger indsættelsessortering til korte stykker og er hurtig på delvist sorterede data, eller introsort, en quicksort, der falder tilbage på heapsort og bruger indsættelsessortering til små dele. Ved mange små heltalsnøgler kan tællesortering eller radixsortering slå dem begge. Boblesortering og udvælgelsessortering er mest undervisningsværktøjer.

Prøv selv

Åbn sorteringskapløbet, og tryk på Afspil. Hver bane er én sortering på den samme liste; tallet til højre tæller dens operationer, og en bane bliver grøn, når den er færdig. Prøv en næsten sorteret liste, en omvendt liste og få unikke værdier, og se rækkefølgen i mål ændre sig. Hver sortering har også sin egen app, hvor du kan gå den igennem i detaljer.

Ofte stillede spørgsmål

Hvad er den hurtigste sorteringsalgoritme?

For generelle data er quicksort og flettesortering (og hybrider bygget på dem, som introsort og Timsort) i gennemsnit hurtigst, med n log n. For små heltalsnøgler er tællesortering og radixsortering endnu hurtigere. For korte eller næsten sorterede lister vinder indsættelsessortering.

Hvorfor kan ingen sammenligningssortering slå n log n?

En liste med n værdier kan stå i n! rækkefølger, og hver sammenligning har to udfald, så der kræves mindst log₂(n!) sammenligninger for at skelne dem alle fra hinanden i værste fald. Det er omkring n log₂ n. Radixsortering og tællesortering undgår denne grænse, fordi de ikke sammenligner.

Hvilke sorteringsalgoritmer er stabile?

Boblesortering, indsættelsessortering, flettesortering, radixsortering og tællesortering er stabile i deres almindelige form. Udvælgelsessortering, quicksort og heapsort er ikke, fordi de flytter værdier over lange afstande.

Hvilke sorteringer kræver ekstra hukommelse?

Flettesortering, radixsortering og tællesortering kræver en buffer, der er omtrent lige så lang som listen. Boblesortering, udvælgelsessortering, indsættelsessortering og heapsort kræver næsten ingen, og quicksort kun lidt til sin rekursion.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Start sorteringskapløbet