Talt
Flytninger
Tællere

  • Tælles
  • Lige flyttet
  • På plads

Mere om tællesortering

Tællesortering

Tællesortering virker, når værdierne er hele tal i et lille interval. Den har én tæller for hver mulig værdi, tæller, hvor ofte hver enkelt forekommer, og ved ud fra antallene præcis, hvor hver værdi hører hjemme. Se tællerne fyldes, mens listen læses, og tømmes igen, når hver værdi flytter ind i sin blok, én flytning ad gangen. 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. Strimlen mellem listen og bufferrækken har én tæller for hver værdi. Felterne tæller de talte værdier, flytningerne og tællerne. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal. 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

  1. Vælg hvor mange søjler og hvordan de starter, eller skriv dine egne hele tal. Prøv en liste med få unikke værdier.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én værdi ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
  3. Hold øje med tællerne: de fyldes op, mens listen læses, og tæller ned, efterhånden som hver værdi placeres.

Sådan virker tællesortering

Lav en tæller for hver værdi fra den mindste til den største. Læs listen én gang, og læg én til tælleren for hver værdi, du ser. Læg så antallene sammen fra den mindste værdi: en værdis blok starter lige efter alle de mindre værdier. Gå til sidst listen igennem igen, flyt hver værdi til den næste ledige plads i sin blok, og kopiér resultatet tilbage.

Hurtig ved et lille interval

Tællesortering læser listen to gange og går tællerne igennem én gang, så arbejdet vokser med n + k: antallet af værdier plus antallet af tællere. For mange værdier i et lille interval, som eksamenspoint fra 0 til 100 eller aldre, slår det enhver sammenligningsbaseret sortering. Ved et bredt interval spilder den tid og hukommelse på tællere, som ingen bruger: tre værdier spredt fra 1 til 1.000.000 ville kræve en million tællere. Det er også det trin, radixsortering gentager for hvert ciffer.

Ofte stillede spørgsmål

Hvordan virker tællesortering?

Den tæller, hvor ofte hver værdi forekommer, lægger antallene sammen for at finde, hvor hver værdis blok starter, og flytter så hver værdi direkte til den næste ledige plads i sin blok. Den sammenligner aldrig to værdier.

Hvornår bør du bruge tællesortering?

Når værdierne er hele tal eller kan laves om til det, og intervallet fra mindste til største ikke er meget større end antallet af værdier: karakterer, aldre, korte koder. Så tager den tid proportional med n + k.

Er tællesortering stabil?

Ja, når værdierne flyttes i listens rækkefølge til den næste ledige plads i deres blok, som her. Det er derfor, radixsortering kan bruge den for hvert ciffer.

Hvorfor ikke bare skrive hver værdi så mange gange, som den blev talt?

For rene tal virker det, og det er endda enklere. Men rigtige data har som regel mere med end nøglen, fx et navn til hvert pointtal, og det går tabt, hvis man kun skriver de talte nøgler. Når selve elementerne flyttes, følger alt med.

Bliver mine tal sendt nogen steder hen?

Nej. Sorteringen kører i din browser, og dine seneste indstillinger bliver 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