Radixsortering
Radixsortering er den skæve blandt sorteringsalgoritmerne: den spørger aldrig, hvilken af to værdier der er størst. Den læser tallene ciffer for ciffer og sorterer dem efter ét ciffer ad gangen med ti spande. Idéen er ældre end computere: sådan virkede sorteringsmaskinerne til hulkort.
Idéen
Sortér tallene efter enercifferet alene. Sortér dem så efter tiercifferet, men på en måde, der holder tal med samme tierciffer i den rækkefølge, det første gennemløb gav dem. Derefter efter hundredecifferet på samme måde. Efter det sidste gennemløb er listen sorteret: hundrederne afgør først, tal med samme hundreder står allerede i rækkefølge efter tierne, og tal med samme tiere i rækkefølge efter enerne.
Ét gennemløb med spande
Hvert gennemløb bruger ti spande, én for hvert ciffer fra 0 til 9. Gå listen igennem fra start til slut, og flyt hvert tal ned i spanden for dets ciffer, bag de tal, der allerede ligger der. Tøm derefter spandene tilbage i listen i rækkefølge, spand 0 først. Det, at tallene flyttes i listens rækkefølge og lægges bagerst i en spand, er det, der holder gennemløbet stabilt. Appen tæller først tallene for hvert ciffer, så spandene kan stå side om side i én række, hver lige efter den forrige: det er en tællesortering på ét ciffer.
Et eksempel
Tag 170, 45, 75, 90, 802, 24, 2, 66. Efter enercifferet: 170, 90, 802, 2, 24, 45, 75, 66. Efter tiercifferet: 802, 2, 24, 45, 66, 170, 75, 90; bemærk, at 802 og 2, begge med tierciffer 0, beholder deres rækkefølge fra det første gennemløb. Efter hundredecifferet: 2, 24, 45, 66, 75, 90, 170, 802. Tre gennemløb over otte tal: 24 læste cifre og 48 flytninger og ikke en eneste sammenligning.
Hvor hurtig er den?
Hvert gennemløb læser ét ciffer i hvert tal og flytter hvert tal to gange, så for n tal med d cifre vokser arbejdet med n · d. En sammenligningsbaseret sortering skal i værste fald bruge mindst omkring n log₂ n sammenligninger, fordi den skal skelne mellem n! mulige rækkefølger med ét ja-nej-spørgsmål ad gangen. Radixsortering er ikke bundet af det, da den aldrig stiller den slags spørgsmål. For mange korte nøgler, som en million tal under 1.000, er tre gennemløb langt mindre arbejde end de omkring 20 millioner sammenligninger, en sammenligningsbaseret sortering ville skulle bruge. For lange nøgler eller få værdier forsvinder fordelen.
LSD og MSD og historien
Versionen her starter med det mindst betydende ciffer (LSD). Den omvendte vej, det mest betydende ciffer først (MSD), deler listen op i spande efter det første ciffer og sorterer hver spand for sig, hvilket passer til strenge af forskellig længde. Radixsortering går tilbage til de hulkortsorterere, der fulgte efter Herman Holleriths tabuleringsmaskiner til den amerikanske folketælling i 1890: en sorterer lod hvert kort falde ned i en af ti lommer efter hullet i én kolonne, og operatørerne kørte bunken igennem én gang pr. kolonne, begyndende med den sidste.
Prøv selv
Åbn appen, og tryk på Trin. Hvert gennemløb tæller først cifrene, og det afmærker spandene 0 til 9 i rækken under listen. Derefter falder tallene ned i deres spande én efter én, med den aktive spand fremhævet, og kopieres tilbage. Skriv dine egne tal op til 999, som eksemplet ovenfor, for at se alle tre gennemløb.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for radixsortering?
O(n · d) for n nøgler med d cifre i en fast base, plus omkostningen ved spandene i hvert gennemløb. Den kræver O(n) ekstra hukommelse til den buffer, spandene ligger i.
Er radixsortering stabil?
LSD-radixsortering er nødt til at være det: den virker kun, fordi hvert gennemløb holder værdier med samme ciffer i den rækkefølge, de kom i. Det endelige resultat er derfor også stabilt.
Kan radixsortering klare negative tal eller decimaltal?
Ikke direkte, men med et trick: forskyd de negative tal, så de alle bliver positive, eller sortér dem for sig og vend dem om. Kommatal kan sorteres efter deres bitmønstre efter en lille omformning.
Hvorfor bruge base 10?
Fordi det er let at følge. Computere sorterer som regel efter 8 eller 16 bit ad gangen, så et 32-bit tal kræver fire eller to gennemløb med 256 eller 65.536 spande.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv radixsortering