Sorteren

In haar column van 1 juli beschreef Ionica Smeets hoe de logistiek van een menselijke keten van de Belgische kerncentrale Tihange naar de Duitse stad Aken haar aan van alles deed denken, behalve kernenergie.

Een van de problemen die bij haar opkwam was het op alfabet sorteren van de schakels in de mensenketen en hoe lang dat zou duren. De sorteermethode waar ze aan dacht bestaat uit het telkens vergelijken van de namen van twee naast elkaar staande personen en die, indien nodig, omwisselen.

Nu kun je zoiets op veel manieren uitvoeren en zo ongeveer het eerste sorteerprogramma dat ik zelf geschreven heb loopt telkens van begin tot eind door de lijst en wisselt verkeerd geordende buren om. Hier is een versie in de taal python (de n is de lengte van de lijst; in python wordt een lijst van lengte n genummerd van 0 tot en met n-1):

for k in range(1,n-1):    
   for l in range(1,n-k): 
      if x[l] < x[l-1]:
         xx = x[l]
         x[l] = x[l-1] 
         x[l-1] = xx

Het programma is iets versneld: als k=1 staat aan het eind van de binnenste loop het grootste element in x[n-1]; als k=2 staat aan het eind van de binnenste loop het op één na grootste element in x[n-2], enzovoort. Dit betekent dat er slechts n-1 binnenloops uitgevoerd hoeven worden die ook steeds korter worden: l loopt telkens maar tot n-k.

Hoe lang duurt het voor het programma klaar is? Neem aan dat we het alfabetisch van Aken naar Tihange willen sorteren. In het ergste geval, als de lijst al alfabetisch gesorteerd is maar net andersom, van Tihange naar Aken dus, moeten er 50000×49999/2 verwisselingen gedaan worden. Dat zijn er, afgerond, 1,25×10⁹, (veel) meer dan een miljard dus.

Aangenomen dat een verwisseling een seconde kost dan zijn we met mijn programmaatje wat meer dan 39 jaar bezig.

Efficiënter?

Het bovenstaande programmaatje implementeert het zogeheten bubble-sort (de grotere elementen `borrelen’ omhoog door de lijst). Bedenk dat dit bij onze mensenketen neerkomt op het volgende: de hoofdorganisator holt iedere keer keer weer langs de keten mensen en laat telkens verkeerd geordende tweetallen omwisselen. Hierbij staat iedereen vrijwel de hele tijd te niksen.

We kunnen die mensen beter zelf wat laten doen door ze als parallelle processoren te gebruiken. Op elk moment laten we de mensen die dan op een evengenummerde plaats staan zich met een buur vergelijken en, zo nodig, van plaats verwisselen. Op de oneven momenten kijken die mensen richting Tihange en op de even momenten richting Aken.

Dus bij stap 1 laten we alle paren (0,1), (2,3), (4,5), … (49998,49999) vergelijken en, indien nodig, wisselen. Bij stap 2 laten we dat de paren (1,2), (3,4), (5,6), … (49997,49998) doen. Dit gebeurt om en om tot de rij gesorteerd is. Dit proces staat, om een voor de hand liggende reden, bekend als odd-even sort.

Omdat we nu telkens 25.000 verwisselingen tegelijk laten doen kost dit `maar’ 50.000 iteraties. En als iedereen goed meewerkt zijn we dus in 50.000 seconden klaar, dat is wat minder dan 14 uur.

Be Sociable, Share!

• 
•