Radix sort

Radix sort is een sorteeralgoritme dat in staat is om verzamelingen van bepaalde elementen te sorteren. Radix sort maakt gebruik van een combinatie van een vaste sorteer-strategie en een apart, tweede sorteer-algoritme (een hulpalgoritme) om een gegeven verzameling elementen te ordenen. Radix sort kan, afhankelijk van het gebruikte hulpalgoritme, zeer efficiënt zijn in het ordenen van een verzameling.

De invoerverzameling

Een van de redenen dat radix sort bijzonder efficiënt uitgevoerd kan worden, is dat radix sort in principe niet algemeen toepasbaar is. Radix sort gaat ervan uit dat de te sorteren elementen getallen zijn, of in ieder geval elementen die qua structuur op getallen lijken -- om preciezer te zijn, radix sort sorteert elementen die bestaan uit cartesische producten van een eindige verzameling V met zichzelf, waarin een totale ordening gedefinieerd is op V en diezelfde ordening door significantie uitgebreid wordt tot het hele, cartesische product.

Voorbeelden van verzamelingen die geordend kunnen worden met radix sort zijn natuurlijke getallen en letterrijen van een bepaalde lengte. Nemen we bijvoorbeeld de natuurlijke getallen die bestaan uit vijf cijfers, dan kunnen we een dergelijk getal opvatten als een element van het cartesisch product $V\times V\times V\times V\times V$, met $V=\{0,1,2,3,4,5,6,7,8,9\}$. Hierin bestaan een ordening op V (0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9) die zich door significantie uitbreidt tot de natuurlijke getallen met vijf cijfers (0xxxx < 5xxxx < 9xxxx, A2xxx < A4xxx, etc.). Radix sort maakt gebruik van deze structuur om elementen te ordenen.

Overigens kan radix sort wel degelijk op algemene verzamelingen toegepast worden, als eerst een afbeelding wordt gedefinieerd van die verzameling naar de natuurlijke getallen.

Het algoritme

Stel dat we een verzameling elementen hebben (A) met een structuur als hierboven beschreven -- zonder verlies van algemeenheid gaan we er verder van uit dat het getallen zijn. Dan kunnen we de elementen als volgt ordenen:

1. Begin aan een kant (het meest significante cijfer, of het minste); beschouw alleen dat cijfer
2. Orden de verzameling alleen maar naar dat cijfer
3. Binnen de ordening die je nu gevonden hebt, orden je op het volgende cijfer
4. Ga zo door totdat je alle cijfers gehad hebt
5. Nu is A geheel geordend

Radix sort is het algoritme die het bovenstaande uitvoert, beginnend met het minst significante cijfer.

Om de bovenstaande stappen uit te voeren, maakt radix sort duidelijk gebruik van de structuur van de te ordenen verzameling. Maar radix sort heeft ook een hulp-algoritme nodig om A te ordenen op één cijfer van de hele rij cijfers. Dit algoritme moet stabiel zijn:

• Zij M een sorteer-algoritme.
• Zij V(M) de verzameling elementen die geordend worden door M.
• Zij v0 en v1 elementen van V.
• Zij idy(v) de positie van v in V voordat M toegepast wordt.
• Zij sidy(v) de positie van v in V nadat M toegepast is.
• Zij Q(v) de functie die een waarde aangeeft voor v; M sorteert V naar groote van Q(v) voor iedere v in V.

Dan is M stabiel als $idy(v_{0})<idy(v_{1})\wedge Q(v_{0})=Q(v_{1})\Rightarrow sidy(v_{0})<sidy(v_{1})$, oftewel als de waardering van v0 en v1 voor M hetzelfde zijn, dan blijven v0 en v1 ten opzichte van elkaar in dezelfde volgorde voor en na toepassing van M.

Stabiliteit van het hulpalgoritme is van levensbelang voor radix sort. Radix sort ordent een verzameling getallen steeds naar een cijfer per keer -- maar maakt absoluut gebruik van de stabiliteit van het hulpalgoritme, doordat de ordening naar eerdere cijfers overeind blijft als op het volgende cijfer gesorteerd wordt. Daarom is de verzameling A geheel geordend nadat op het meest significante cijfer geordend is.

Bekijken we een voorbeeld:

(A) (B) (C) (D)
329 720 720 329
457 355 329 355
657 436 436 436
839 → 457 → 839 → 457
436 657 355 657
720 329 457 720
355 839 657 839

(A) Willekeurig
(B) A is gesorteerd op laatste cijfer
(C) B is gesorteerd op middelste cijfer
(D) C is gesorteerd op eerste cijfer

Merk op dat in het bovenstaande voorbeeld, kolom nummer i correct geordend is op de laatste i cijfers. Nemen we de derde kolom (nummer 2) van links en negeren we het eerste cijfer, dan valt direct op dat de kolom correct geordend is naar de laatste twee cijfers. De stabiliteit van het hulpalgoritme zorgt ervoor dat deze "onderlinge ordening" in stand blijft zodra er ook op het volgende cijfer geordend is.

Merk ook op dat het sorteren veel meer moeite gekost had als we van meest significant naar minst hadden gesorteerd. Met die volgorde is stabiliteit niet een voldoende eis voor het hulpalgoritme -- in plaats van de relatieve volgorde van twee elementen van gelijke orde in stand te houden, moeten we bij ordening van meest naar minst significant zelfs de gehele ordening tussen stappen bij elkaar houden. Dat zou betekenen dat we in iedere stap de verzameling A moesten onderverdelen in stukken met dezelfde n cijfers aan de linkerkant en die stukken apart intern zouden moeten ordenen.

Formeel bewijs van correctheid van radix sort

Het klassieke bewijs van correctheid voor radix sort verloopt door middel van volledige inductie naar het aantal cijfers n van de elementen van de te ordenen verzameling.

Basis

Zij n = 0. Voor dit geval is radix sort correct: de lege verzameling is per definitie geordend.

Inductiehypothese

Toepassing van radix sort op een verzameling getallen ter lengte N ordent de verzameling op correcte wijze.

Stap

Zij n = N + 1. Dan kan radix sort n-maal toegepast worden en is de verzameling volgens de inductie hypothese correct geordend tot op de n minst significante cijfers. Passen we nu het hulp-algoritme toe op het n+1-ste, meest significante cijfer C. Voor ieder paar elementen A en B van de verzameling zijn er nu twee mogelijkheden:

• $C_{A}<C_{B}$ (of omgekeerd). In dit geval worden (door de correctheid van het hulp-algoritme) A en B zo geordend dat A voor B komt te staan, wat correct is omdat $C_{A}<C_{B}$.
• $C_{A}=C_{B}$. Omdat het meest significante cijfer geen onderscheidend vermogen heeft voor A en B, stonden A en B al goed ten opzichte van elkaar -- ze waren al geordend naar hun minder significante cijfers. Omdat het hulp-algoritme stabiel is, blijft hun relatieve volgorde behouden en is radix sort ook in dit geval correct.

Radix sort in code

In het algemeen ziet radix sort er als volgt uit:

|[ const A : verzameling van natuurlijke getallen;
 d : integer; {d = het aantal cijfers in ieder element van A}
 var n : integer;
|
 n := 1;
 do n <= d -> sorteer A naar cijfer nummer n met een stabiel hulpalgoritme od
 ]|

De efficiëntie van radix sort

Om getallen van d cijfers te sorteren, zijn d aanroepen van het hulpalgoritme nodig. Daarmee is de efficiëntie van radix sort $\mathbb {O} (dK)$, met K de efficiëntie van het hulpalgoritme. Is dit hulpalgoritme lineair (zoals met counting sort bijvoorbeeld mogelijk is), dan is radix sort ook lineair.

De naam radix sort

Radix sort werd vaak toegepast in sorteermachines voor ponskaarten. Het "hulpalgoritme" van radix sort bestond er hier in om bij ieder geponst cijfer naar de waarde van dat cijfer te kijken en de kaart dan in een bijbehorend bakje te deponeren. Radix sort zelf bestond dan uit het samenvoegen van de kaarten uit verschillende bakjes in de juiste volgorde en nog eens verdelen over bakjes, naar het volgende cijfer.

Voor deze methode waren precies evenveel bakjes nodig als er cijfers waren om getallen mee te maken -- dit aantal heet de radix of het grondtal van een getallenstelsel. Vandaar radix sort.

Een code-voorbeeld

De volgende code is een demonstratie-implementatie van radix sort in Pascal. Dit programma leest van de standaard invoer een bestand in met daarin een getal per regel -- het eerste getal het aantal cijfers van de andere getallen, de rest van de getallen de te sorteren verzameling.

De gegeven implementatie simuleert de eerder genoemde sorteer-machines, door gebruik te maken van de bakjes-methode als hulpalgoritme.

 program radix_demo;

 {$R-,I+}

 procedure radixsort(var data:array of integer;decimalen:integer);

 const RADIX=10; {Gebruik het decimale stelsel.}

 type Pbak=^bak;
 bak=array[1..1] of integer;

 var bakken:array[0..RADIX-1] of Pbak;
 bakken_teller:array[0..RADIX-1] of integer;
 deeltal:integer;

 procedure sorteer_positie(positie:integer);

 {Loop de data door en sorteer deze op de meegegeven positie. Dit sorteren
 gebeurt door de dataelementen in de bakken te stoppen. Hierna worden de
 bakken in volgorde afgelopen en de inhoud terug in de dataarray geplaatst
 waardoor een gesorteerde lijst ontstaat.}

 var i,j,p,temp:integer;

 begin
 {Leeg de bakken.}
 for i:=0 to RADIX-1 do
 bakken_teller[i]:=0;
 {Plaats de data in de bakken.}
 for i:=low(data) to high(data) do
 begin
 temp:=(data[i] div deeltal) mod RADIX;
 inc(bakken_teller[temp]);
 bakken[temp]^[bakken_teller[temp]]:=data[i];
 end;
 deeltal:=deeltal*RADIX;
 {Plaats de inhoud van de bakken terug in data.}
 p:=low(data);
 for i:=0 to RADIX-1 do
 for j:=1 to bakken_teller[i] do
 begin
 data[p]:=bakken[i]^[j];
 inc(p);
 end;
 end;

 var i:integer;

 begin
 {Initialiseer deeltal.}
 deeltal:=1;
 {Maak de bakken aan. Meest extreme situatie is dat alle dataelementen
 in 1 bak terechtkomen. Dus dat is de hoeveelheid gevraagd geheugen.}
 for i:=0 to RADIX-1 do
 getmem(bakken[i],(1+high(data)-low(data))*sizeof(integer));
 for i:=1 to decimalen do
 sorteer_positie(i);
 {Breek de bakken af.}
 for i:=0 to RADIX-1 do
 freemem(bakken[i],(1+high(data)-low(data))*sizeof(integer));
 end;


 {DEMO: Het volgende hoofdprogramma leest van de standaard invoer:
 - Het aantal decimalen
 - Het aantal te sorteren getallen
 - De te sorteren getallen zelf.
 Op de standaard uitvoer wordt de gesorteerde lijst uitgevoerd.}

 var data:array of integer;
 aantal_getallen,decimalen,i,x:integer;

 begin
 readln(decimalen);
 readln(aantal_getallen);
 setlength(data,aantal_getallen);
 for i:=0 to aantal_getallen-1 do
 readln(data[i]);
 radixsort(data,decimalen); {Start sortering}
 for i:=low(data) to high(data) do
 writeln(data[i]);
 end.