title: Radix sort
text: 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 , met . 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:
  
   Begin aan een kant (het meest significante cijfer, of het minste); beschouw alleen dat cijfer
   Orden de verzameling alleen maar naar dat cijfer
   Binnen de ordening die je nu gevonden hebt, orden je op het volgende cijfer
   Ga zo door totdat je alle cijfers gehad hebt
   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 , 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:
    (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 .
   . 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 , 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.
  
  Sorteeralgoritme