- Spand i brug
- Lige flyttet
- Kopieret tilbage
- På plads
Radixsortering
Radixsortering sorterer hele tal uden nogensinde at sammenligne to af dem. Den sorterer listen efter enercifferet, så efter tiercifferet og så efter hundredecifferet, og hver gang flytter den værdierne ned i ti spande og kopierer dem tilbage i rækkefølge. Se spandene blive fyldt i rækken under listen, én flytning ad gangen, og se listen blive sorteret efter flere og flere cifre. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå én flytning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Spandene 0 til 9 står side om side i rækken under listen. Felterne tæller læste cifre, flytninger og gennemløb. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal op til 999. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.
Sådan virker det
- Vælg hvor mange søjler og hvordan de starter, eller skriv dine egne hele tal op til 999 for at se gennemløbet for hundrederne.
- Tryk på Afspil, eller brug Trin og Tilbage for at flytte én værdi ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
- Følg hvert gennemløb: tæl cifrene, flyt hver værdi ned i dens spand, og kopiér så spandene tilbage.
Sådan virker radixsortering
Se kun på det sidste ciffer i hvert tal, og sortér listen efter det: læg hvert tal i en af ti spande, 0 til 9, i den rækkefølge de kommer, og kopiér så spandene tilbage én efter én. Gør det samme med tiercifferet og derefter hundredecifferet. Fordi hvert gennemløb bevarer rækkefølgen af tal med samme ciffer, afgør de tidligere gennemløb stadig rækkefølgen mellem dem, og efter det sidste gennemløb er hele listen sorteret.
Ingen sammenligninger overhovedet
Sammenligningsbaserede sorteringer skal i værste fald bruge mindst omkring n log₂ n sammenligninger, uanset hvilket smart trick de bruger. Radixsortering går uden om den grænse ved at læse cifre i stedet: hvert gennemløb læser ét ciffer i hver værdi og flytter hver værdi to gange, så d cifre kræver d gennemløb, og arbejdet vokser med n · d. For lange lister med korte nøgler betaler det sig: en million tal op til 999 kræver tre gennemløb, hvor en sammenligningsbaseret sortering skal bruge omkring 20 millioner sammenligninger. Prisen er, at den kun virker for nøgler af cifre eller tegn, og at den kræver plads til spandene.
Ofte stillede spørgsmål
Hvordan virker radixsortering?
Den sorterer tallene efter deres sidste ciffer, så efter cifferet før det, og så videre op til det første ciffer. Hvert gennemløb lægger tallene i ti spande efter det ciffer uden at ændre deres rækkefølge og kopierer spandene tilbage. Efter gennemløbet for det mest betydende ciffer er listen sorteret.
Hvorfor starte med det sidste ciffer?
Fordi hvert gennemløb er stabilt: tal med samme ciffer beholder den rækkefølge, de tidligere gennemløb gav dem. Så det sidste gennemløb, på det første ciffer, afgør rækkefølgen, og ved lige cifre afgør de cifre, der allerede er sorteret. Det kaldes LSD-radixsortering (least significant digit, det mindst betydende ciffer).
Er radixsortering hurtigere end quicksort?
Det kan den være, for mange korte nøgler: arbejdet vokser med antallet af værdier gange antallet af cifre, uden n log n. For få værdier, meget lange nøgler eller data, der ikke består af cifre, er quicksort og merge sort som regel hurtigere og enklere.
Hvordan hænger den sammen med tællesortering?
Hvert gennemløb i radixsortering er en tællesortering (counting sort) på ét ciffer: tæl hvor mange værdier der har hvert ciffer, regn ud hvor hver spand starter, og flyt værdierne derhen i rækkefølge.
Bliver mine tal sendt nogen steder hen?
Nej. Sorteringen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor