Gelezen cijfers
Verplaatsingen
Ronde

  • Bak in gebruik
  • Net verplaatst
  • Teruggekopieerd
  • Op zijn plek

Meer over radix sort

Radix sort

Radix sort sorteert gehele getallen zonder er ooit twee te vergelijken. Het sorteert de lijst op het cijfer van de eenheden, dan op dat van de tientallen, dan op de honderdtallen, en zet de waarden telkens in tien bakken en kopieert ze op volgorde terug. Zie de bakken in de rij onder de lijst vollopen, één verplaatsing per keer, en zie de lijst op steeds meer cijfers gesorteerd raken. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per verplaatsing te gaan. Sleep de stappenschuif om ergens naartoe te springen. De bakken 0 tot en met 9 staan naast elkaar in de rij onder de lijst. De tegels tellen gelezen cijfers, verplaatsingen en rondes. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen tot 999. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies hoeveel staven en hoe ze beginnen, of typ je eigen gehele getallen tot 999 om ook de ronde voor de honderdtallen te zien.
  2. Druk op Afspelen, of gebruik Stap en Terug om per waarde te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
  3. Volg elke ronde: tel de cijfers, zet elke waarde in haar bak en kopieer de bakken dan terug.

Hoe radix sort werkt

Kijk alleen naar het laatste cijfer van elk getal en sorteer de lijst daarop: zet elk getal in een van tien bakken, 0 tot en met 9, in de volgorde waarin ze komen, en kopieer de bakken dan een voor een terug. Doe hetzelfde met het cijfer van de tientallen, dan met de honderdtallen. Omdat elke ronde de volgorde bewaart van getallen met hetzelfde cijfer, bepalen de eerdere rondes nog steeds hun onderlinge volgorde, en na de laatste ronde is de hele lijst gesorteerd.

Helemaal geen vergelijkingen

Vergelijkende sorteeralgoritmen hebben in het slechtste geval minstens zo'n n log₂ n vergelijkingen nodig, welke slimme truc ze ook gebruiken. Radix sort omzeilt die grens door cijfers te lezen: elke ronde leest één cijfer van elke waarde en verplaatst elke waarde twee keer, dus d cijfers kosten d rondes en het werk groeit met n · d. Voor lange lijsten met korte sleutels loont dat: een miljoen getallen tot 999 kosten drie rondes, waar een vergelijkend algoritme zo'n 20 miljoen vergelijkingen nodig heeft. De prijs is dat het alleen werkt voor sleutels die uit cijfers of tekens bestaan, en dat het ruimte voor de bakken nodig heeft.

Veelgestelde vragen

Hoe werkt radix sort?

Het sorteert de getallen op hun laatste cijfer, dan op het cijfer daarvoor, en zo verder tot het eerste cijfer. Elke ronde zet de getallen op dat cijfer in tien bakken, zonder hun volgorde te veranderen, en kopieert de bakken terug. Na de ronde voor het meest significante cijfer is de lijst gesorteerd.

Waarom beginnen bij het laatste cijfer?

Omdat elke ronde stabiel is: getallen met hetzelfde cijfer houden de volgorde die de eerdere rondes ze gaven. De laatste ronde, op het eerste cijfer, bepaalt dus de volgorde, en bij gelijke cijfers beslissen de cijfers die al gesorteerd zijn. Dit heet LSD radix sort (least significant digit, het minst significante cijfer).

Is radix sort sneller dan quicksort?

Dat kan, bij veel korte sleutels: het werk groeit met het aantal waarden maal het aantal cijfers, zonder n log n. Bij weinig waarden, heel lange sleutels of gegevens die niet uit cijfers bestaan, zijn quicksort en merge sort meestal sneller en eenvoudiger.

Wat is het verband met counting sort?

Elke ronde van radix sort is een counting sort op één cijfer: tel hoeveel waarden elk cijfer hebben, bereken waar elke bak begint en zet de waarden daar op volgorde neer.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor