Tællesortering
Tællesortering sorterer slet ikke ved at sammenligne værdier. Hvis du ved, at hver værdi er et helt tal mellem for eksempel 1 og 40, kan du bare tælle, hvor mange der er af hver, og ud fra antallene regne ud, hvor hver enkelt hører hjemme. Ved et lille interval er det omtrent så hurtigt, som sortering kan blive.
Tæl
Find den mindste og største værdi, og lav én tæller for hver værdi derimellem, alle med start i nul. Læs listen én gang fra start til slut, og læg én til tælleren for hver værdi, du ser. Tællerne danner nu et histogram: hvor mange 1-taller, hvor mange 2-taller og så videre. Med n værdier og k tællere tager det n trin.
Læg sammen
Værdierne lig med den mindste værdi kommer først, så deres blok starter på plads 1. Den næste værdis blok starter lige efter dem, og så videre: hver blok starter efter summen af alle antallene før den. Disse løbende summer, kaldet præfikssummer, gør histogrammet til et kort over den sorterede liste. Det tager k trin.
Placér
Læs listen en gang til, og flyt hver værdi til den næste ledige plads i sin blok. Fordi værdierne flyttes i den rækkefølge, de står i, beholder lige store værdier deres oprindelige rækkefølge: tællesortering er stabil. Kopiér bufferen tilbage, og listen er sorteret. Appen viser hver tæller gå ned igen, efterhånden som dens værdier placeres.
Et eksempel
Tag 4, 1, 3, 4, 2, 1, 4. Tællerne for 1 til 4 ender på 2, 1, 1 og 3. Sammenlægningen giver blokkene: 1-tallerne på plads 1 og 2, 2-tallet på plads 3, 3-tallet på plads 4 og 4-tallerne på plads 5 til 7. Når værdierne placeres i listens rækkefølge, fås 1, 1, 2, 3, 4, 4, 4: 7 værdier talt, 14 flytninger, 4 tællere og ingen sammenligninger.
Hvornår du skal bruge den
Det samlede arbejde vokser med n + k. Når k er lille i forhold til n, som tusind eksamenspoint fra 0 til 100, er tællesortering hurtigere end enhver sammenligningsbaseret sortering, der skal bruge omkring n log₂ n sammenligninger. Når intervallet er bredt, er den spild: nogle få værdier spredt op til en million kræver en million tællere. Radixsortering løser det ved at køre tællesortering én gang pr. ciffer, så hvert gennemløb kun skal bruge ti tællere. Harold Seward beskrev tællesortering sammen med radixsortering i 1954.
Udforsk den
Åbn appen, og tryk på Trin. Strimlen mellem listen og bufferrækken viser én tæller pr. værdi. Se tællerne fyldes, mens listen læses, blokkene dukke op i bufferen, når antallene lægges sammen, og tællerne gå ned igen, når værdierne placeres. Vælg få unikke værdier for at se store blokke, eller skriv tal langt fra hinanden for at se, hvor mange tællere et bredt interval kræver.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten af tællesortering?
O(n + k) for n værdier og k mulige værdier, og O(n + k) ekstra hukommelse til tællerne og bufferen.
Hvorfor er tællesortering ikke altid hurtigst?
Fordi dens omkostning afhænger af værdiernes interval, ikke kun af hvor mange de er. Hvis intervallet er meget større end listen, bliver de fleste tællere ved nul, og tiden og hukommelsen går til spilde.
Kan tællesortering håndtere negative tal?
Ja. Tællerne går fra den mindste værdi til den største, så træk den mindste værdi fra for at få en tællers indeks. Appen gør det samme.
Er tællesortering stabil?
Ja, så længe værdierne flyttes i listens rækkefølge til den næste ledige plads i deres blok. Det afhænger radixsortering af.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv tællesortering