Radix sort

Radix sort is de vreemde eend onder de sorteeralgoritmen: het vraagt nooit welke van twee waarden groter is. Het leest de getallen cijfer voor cijfer en sorteert ze op één cijfer tegelijk, met tien bakken. Het idee is ouder dan computers: zo werkten de sorteermachines voor ponskaarten.

Staven van een lijst boven een rij van tien bakken met de labels 0 tot en met 9, een waarde die in de bak voor haar laatste cijfer valt
Staven van een lijst boven een rij van tien bakken met de labels 0 tot en met 9, een waarde die in de bak voor haar laatste cijfer valt

Het idee

Sorteer de getallen alleen op het cijfer van de eenheden. Sorteer ze dan op het cijfer van de tientallen, maar zo dat getallen met hetzelfde cijfer van de tientallen in de volgorde blijven die de eerste ronde ze gaf. Dan op de honderdtallen, op dezelfde manier. Na de laatste ronde is de lijst gesorteerd: de honderdtallen beslissen eerst, gelijke honderdtallen staan al op volgorde van hun tientallen, en gelijke tientallen op volgorde van hun eenheden.

Eén ronde, met bakken

Elke ronde gebruikt tien bakken, één voor elk cijfer van 0 tot en met 9. Loop de lijst van begin tot eind door en zet elk getal in de bak voor zijn cijfer, achter de getallen die er al in zitten. Leeg de bakken daarna op volgorde terug in de lijst, bak 0 eerst. Doordat de getallen in lijstvolgorde verplaatst en achter in een bak gezet worden, blijft de ronde stabiel. De app telt eerst de getallen per cijfer, zodat de bakken naast elkaar in één rij passen, elk direct na de vorige: dat is een counting sort op één cijfer.

Een voorbeeld

Neem 170, 45, 75, 90, 802, 24, 2, 66. Op het cijfer van de eenheden: 170, 90, 802, 2, 24, 45, 75, 66. Op het cijfer van de tientallen: 802, 2, 24, 45, 66, 170, 75, 90; let op dat 802 en 2, allebei met een 0 bij de tientallen, hun volgorde uit de eerste ronde houden. Op het cijfer van de honderdtallen: 2, 24, 45, 66, 75, 90, 170, 802. Drie rondes over acht getallen: 24 gelezen cijfers en 48 verplaatsingen, en geen enkele vergelijking.

Hoe snel is het?

Elke ronde leest één cijfer van elk getal en verplaatst elk getal twee keer, dus voor n getallen met d cijfers groeit het werk met n · d. Een vergelijkend sorteeralgoritme heeft in het slechtste geval minstens zo'n n log₂ n vergelijkingen nodig, omdat het n! mogelijke volgordes moet onderscheiden met telkens één ja-neevraag. Radix sort zit niet aan die grens vast, omdat het zulke vragen nooit stelt. Bij veel korte sleutels, zoals een miljoen getallen onder 1.000, zijn drie rondes veel minder werk dan de ongeveer 20 miljoen vergelijkingen die een vergelijkend algoritme nodig zou hebben. Bij lange sleutels of weinig waarden verdwijnt het voordeel.

LSD en MSD, en geschiedenis

De versie hier begint bij het minst significante cijfer (LSD, least significant digit). De omgekeerde aanpak, met het meest significante cijfer eerst (MSD), verdeelt de lijst over bakken op het eerste cijfer en sorteert elke bak apart, wat goed past bij strings van verschillende lengte. Radix sort gaat terug op de ponskaartsorteerders die volgden op de tabulatormachines van Herman Hollerith voor de Amerikaanse volkstelling van 1890: een sorteerder liet elke kaart in een van tien vakken vallen volgens het gat in één kolom, en operators haalden de stapel één keer per kolom door de machine, te beginnen bij de laatste.

Een Hollerith-ponskaarttabulator in het Computer History Museum, van het type dat bij de Amerikaanse volkstelling van 1890 werd gebruikt. Operators lieten een stapel per kolom één keer door een sorteerder lopen, de voorloper van radixsort.
Een Hollerith-ponskaarttabulator in het Computer History Museum, van het type dat bij de Amerikaanse volkstelling van 1890 werd gebruikt. Operators lieten een stapel per kolom één keer door een sorteerder lopen, de voorloper van radixsort.

Probeer het zelf

Open de app en druk op Stap. Elke ronde telt eerst de cijfers, en daarmee worden de bakken 0 tot en met 9 in de rij onder de lijst afgebakend. Daarna vallen de getallen een voor een in hun bakken, met de actieve bak gemarkeerd, en worden ze teruggekopieerd. Typ je eigen getallen tot 999, zoals het voorbeeld hierboven, om alle drie de rondes te zien.

Veelgestelde vragen

Wat is de tijdcomplexiteit van radix sort?

O(n · d) voor n sleutels van d cijfers in een vaste basis, plus de kosten van de bakken per ronde. Het heeft O(n) extra geheugen nodig voor de buffer waarin de bakken staan.

Is radix sort stabiel?

LSD radix sort moet wel: het werkt alleen omdat elke ronde waarden met hetzelfde cijfer in de volgorde houdt waarin ze binnenkwamen. Het eindresultaat is dus ook stabiel.

Kan radix sort negatieve getallen of kommagetallen aan?

Niet direct, maar wel met een truc: verschuif negatieve getallen zodat ze allemaal positief zijn, of sorteer ze apart en keer ze om. Drijvendekommagetallen kunnen na een kleine omzetting op hun bitpatroon gesorteerd worden.

Waarom basis 10?

Omdat dat makkelijk te volgen is. Computers sorteren meestal op 8 of 16 bits tegelijk, dus een 32-bits getal kost vier of twee rondes, met 256 of 65.536 bakken.

Klaar om het te proberen?

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

Probeer radix sort