donderdag 14 april 2011

Dansend sorteren

Omwille van de interactieve interface waarmee we met onze PC’s communiceren, zouden we wel eens durven vergeten dat computers in feite niets anders zijn dan snelle gegevens-verwerkende machines.
Bij het verwerken van gegevens is het sorteren ervan een belangrijke bewerking.
Er zijn dan ook in de loop der jaren verschillende sorteeralgoritmen uitgedokterd.
Dat wil zeggen: methodes, werkwijzen, waarmee data efficiënt kunnen geordend worden.
De te kiezen sorteermethode hangt in hoge mate samen met de aard en de hoeveelheid gegevens die moeten gesorteerd worden.

De Roemeense Sapientia Unversity in het Transylvaanse Tirgu Mores, heeft een wel heel bijzondere didactische methode ontwikkeld om de verschillende sorteeralgoritmen aan haar studenten duidelijk te maken: de sorteerwijze wordt geïllustreerd door genummerde volksdansers!
Ze hebben er leuke en erg leerzame filmpjes van gemaakt en die op hun YouTube-kanaal voor iedereen toegankelijk gemaakt.
Ik presenteer er jullie vandaag twee met een beetje uitleg.
De andere kan je op hun kanaal zelf eens bekijken.

Insertion sort
Een willekeurige rij getallen van 0 tot 9 wordt volgens toenemende grootte gesorteerd.
Eerst worden de eerste twee getallen met elkaar vergeleken en volgens grootte geordend. Als deze op hun plaats staan, wordt het derde element vergeleken met het tweede en ook op de juiste plaats gezet. Het tweede wordt weer vergeleken met het eerste enz. Dit doen we totdat alle getallen in de juiste volgorde staan.
En dit alles op de tonen en de sierlijke pasjes van een Roemeense volksdans



Selection sort
Ook hier wordt een rij getallen van 0 tot 9 wordt volgens toenemende grootte gesorteerd.



Er wordt eerst gezocht naar het kleinste getal in de rij.
Als dat niet zelf het eerste is, wordt het verwisseld met het eerste getal in de rij.
Deze twee stappen worden herhaald met de rest van de rij getallen.
Zigeunermuziek moet hier het sorteergebeuren opvrolijken. 
Dat dit algoritme minder efficiënt (trager) werkt dan de insertion sort, wordt na een tijdje geïllustreerd: de weergavesnelheid van het filmpje wordt opgedreven
Maar daardoor verwordt het mooie melodietje tot een stomme tjingel tjangel.

Ja, time is money, zeker bij sorteren…

Geen opmerkingen:

Een reactie posten