Sorteren is ook een volksdans

De Sapientia Universiteit in Roemenië heeft een aantal bekende sorteertechnieken in beeld gebracht als volksdans. Een hartveroverende manier om computerwetenschap te populariseren. Sorteren is makkelijk. De maanden van het jaar op alfabetische volgorde? Met de hand is dat zo gepiept. Het sorteren van grote aantallen records, bijvoorbeeld een bevolkingsregister, is ook niet moeilijk. Wel tijdrovend en vervelend. Dan is het mooi als een computer de klus kan overnemen. Maar daarvoor is een wiskundig algoritme nodig, een voorschrift dat, indien stug stap voor stap uitgevoerd, tot het juiste resultaat leidt. De Sapientia Universiteit in Transsylvanië toont met gevolksdanste visualisaties de methoden en hoe ze werken.

Bijvoorbeeld Bubblesort. Dit is een van de oudste algoritmes, gepubliceerd in 1956. Tien dansers in klederdracht met rugnummers 0 tot en met 9 stellen zich op in een duidelijk niet gesorteerde rij. Op de tonen van een Hongaarse volksdans (Transsylvanië is het Hongaarse deel van Roemenië) beginnen eerst de meest linkse twee dansers, de 0 en de 3, om elkaar heen te draaien. Het is duidelijk dat hun getalswaarde wordt vergeleken en na een paar maten neemt de kleinste de uiterst linkse plaats in en de grootste van de twee, de 3 dus, de plek daarnaast. Nu mag de 3 zich vergelijken met het getal aan de andere kant. Dat blijkt de 1 te zijn en de twee getallen ruilen van plaats. De 0 en de 1 staan nu al goed. De 3 is daarmee omhoog ‘gebubbeld’ in de richting van de juiste plaats maar komt nu de 7 tegen dus de opmars wordt tijdelijk gestuit. 7 is immers groter dan 3. Zo worden steeds naburige paren vergeleken en zo nodig verwisseld, net zolang tot de rij in de juiste volgorde staat.

Sorteren blijkt op tientallen manieren te kunnen. Al die manieren hebben voor- en nadelen. Bubblesort is in weinig regels te programmeren maar er zijn relatief veel stappen nodig. Afhankelijk van de beginsituatie (die al goed gesorteerd kan zijn) is het aantal benodigde stappen maximaal het kwadraat van het aantal te sorteren eenheden. Op het YouTube-kanaal AlgoRythmics worden nog vijf algoritmes met muziek en dans in beeld gebracht: Insertsort, Selectsort, Shellsort, Mergesort en Quicksort. De makers hebben behalve een YouTube-kanaal ook een Facebookpagina, beide staan vol enthousiaste reacties. Helaas is er geen informatie over de eigenschappen van de sorteertechnieken. Die staat gelukkig op Wikipedia.

Herbert Blankesteijn

Bekijk de video op nrc.nl/bekijks