På Datalogisk Institut på Københavns Universitet uddannes nogle af Danmarks skarpeste it-hjerner. I spidsen for dem står Martin Zachariasen, der er institutleder på DIKU.
Egentlig spurgte vi ham om hvilken programmør, der var hans yndling, men på eget initiativ fik han bøjet samtalen over i en mere teoretisk retning.
"Faktisk kunne jeg tænke mig, at temaet blev min yndlingsalgoritme. Selvom der er mange at vælge imellem, vælger jeg Quicksort," responderede Martin Zachariasen på Computerworlds henvendelse.
"Grunden til at jeg kom til at tænke på det er, fordi jeg for 20 år siden var studerende på DIKU, og på et algoritme-kursus blev Quicksort præsenteret som den første. Det er en klassiker, som alle dataloger og mange andre it-folk har stiftet bekendtskab med," fortæller han.
"Den har lidt kult over sig. Det er en af de algoritmer, man altid husker, selvom den ikke hører til blandt de mest elegante. Navnet er samtidig utrolig godt valgt."
"Det der gør den til noget helt specielt er, at den er enkel, nem at forklare, og så kan den skrives i få linjer kode. Samtidig kan den illustrere mange algoritmiske principper, og så er den praktisk anvendelig," siger Martin Zachariasen.
To talbunker giver fart
Quicksort er en klassisk rekursiv sorteringsprocedure og den er bredt anerkendt som en af de bedste sorteringsteknikker, selv om den stammer helt tilbage fra 1962, da it-branchen stadig var i sin vorden.
"Trods den høje alder løser Quicksort stadig en meget fundamental opgave indenfor problemløsning. Sortering er stadig noget af det første, man lærer inden for algoritmelære," fortæller Martin Zachariasen.
Quicksort er yderst effektiv til sortering af eksempelvis, strenge eller tal, og den fungerer kort fortalt ved at opdele mængden af enheder i to bunker.
Har man eksempelvis 100 tal, deler algoritmen dem op i to dele, hvor den ene er mindre end eller lig med 50 og den anden del er større end eller lig med 50. Denne proces gentages så igen og igen indtil tallene er sorteret.
"Metoden er enkel, og den demonstrerer samtidig en masse ting om algoritme-disciplinen," siger han.
"Samtidig opfører denne algoritme sig rigtig godt på en moderne computer, eksempelvis i arbejdet med cache i cpu'en. Derfor bruges den stadig i meget stort omfang."
Quicksort har desuden sin helt egen musikvideo, der illustrerer, hvordan den virker.
