De humor van de IT-crowd is vaak technisch en onconventioneel – net als de hier genoemde sorteeralgoritmes, die niet per se praktisch bedoeld zijn, maar kunnen bijdragen aan de sfeer bij de volgende scrum.
De creatieve kant van sorteren
Zelf sorteeralgoritmes schrijven is een goede manier om te leren programmeren. Je behandelt het probleem, werkt een oplossing uit en implementeert die uiteindelijk in de gewenste taal. Op die manier leer je problemen in de informatica op te lossen door de eenvoudige en praktische taak om waarden in de juiste volgorde te zetten.
Dat hoeft geen gortdroge materie te zijn door alleen te kijken naar bekende efficiënte algoritmes zoals Mergesort, Quicksort [1] en Timsort [2]. Zelfs slechte of onduidelijke algoritmes hebben een educatieve waarde als je analyseert waarom ze geen (goede) oplossing zijn. En ze kunnen vermakelijk zijn.
Daarom belichten we deze keer de creativiteit en humor in de IT-branche aan de hand van het voorbeeld van bijzondere sorteeralgoritmes. We hebben forums afgestruind, boeken doorgebladerd en tientallen jaren oude papers gelezen om de achtergrondverhalen te vinden.
De algoritmes die we hier noemen kunnen globaal in drie categorieën verdeeld worden. Klassiekers, waarvan sommige al tientallen jaren de ronde doen en te vinden zijn op vrijwel elke ranglijst of video over vreemde sorteeralgoritmes, bijzonder snelle of extreem langzame methoden, en tot slot sorteeralgoritmes met grappige namen die niet eens een poging doen om gegevens goed te ordenen.
We hebben een aantal procedures opnieuw geprogrammeerd in Python en ze op de GitHub-repository voor deze artikelreeks gezet (zie de link bij dit artikel), terwijl we ons hebben onthouden van het implementeren van sommige andere om de balans van ons universum niet te verstoren.
Bogosort
Bogosort, ook bekend als Stupidsort, Randomsort, Dumbsort en andere namen, mag op geen enkele ranglijst van bijzondere sorteeralgoritmes ontbreken. Dat zijn allemaal namen die direct de (in)efficiëntie van die methode aangeven.
Het algoritme kan in slechts een paar regels beschreven worden. Bogosort schudt gewoon de gegevens die gesorteerd moeten worden totdat de lijst door toeval volledig gesorteerd is. Het is alsof je een pak kaarten steeds opnieuw in de lucht gooit en ze dan willekeurig oppakt in de hoop dat ze uiteindelijk in de juiste volgorde komen te liggen. Dat is de definitie van Bogosort uit het boek The New Hacker’s Dictionary van Eric S. Raymond uit 1991.
De computerwetenschappers Hermann Gruber, Markus Holzer en Oliver Ruepp namen Bogosort met een knipoog onder de loep en publiceerden hun resultaten over de snelheid van langzame sorteeralgoritmes in een paper met de mooie naam Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. Het paper en meer materiaal over bijzondere algoritmes kun je vinden bij de link.
Bogosort kan compact worden geïmplementeerd in Python dankzij de overzichtelijke functies:
def bogosort(a):
while True:
random.shuffle(a)
if check_if_sorted(a):
return aBogosort krijgt een array a met getallen, die willekeurig door elkaar gehusseld worden. Het husselen wordt uitgevoerd door de functie shuffle() uit de Python-bibliotheek random.
Na elke run wordt de lijst doorgegeven aan de hulpmethode check_if_sorted(), die controleert of de lijst gesorteerd is.
def check_if_sorted(a):
for n in range(len(a) - 1):
if a[n] > a[n + 1]:
return False
return TrueHelaas zijn we er niet in geslaagd om de creatieve bedenker te vinden aan wie we die buitengewone prestatie te danken hebben. Dat spoor loopt ergens in de jaren tachtig dood.
In die tijd werden andere verbazingwekkende papers gepubliceerd, zoals Pessimal Algorithms and Simplexity Analysis uit 1984 van Andrei Broder en Jorge Stolfi. Dat bevat een verzameling wonderbaarlijk langzame algoritmes, waaronder Slowsort (zie de link).
Het is de moeite waard om het artikel eens rustig door te nemen, want het staat vol toespelingen en kwinkslagen. Kijk bijvoorbeeld eens naar de referenties.
Het paper geeft ook antwoord op de vraag waarom langzame processen überhaupt nodig zijn. Stel dat je een trip naar Parijs maakt en items moet sorteren, dan zou een algoritme als Slowsort een goede keuze zijn – je wilt daar immers zo lang mogelijk mee bezig blijven.
Quantumsort
De eenvoudige aanpak van Bogosort heeft de creativiteit van menig grappenmaker geprikkeld en er zijn veel andere methoden ontwikkeld op basis van Bogosort. Eén daarvan is Quantumsort, soms ook Quantum-Bogosort genoemd. Dat tilt de absurditeit van Bogosort naar een heel nieuw niveau.
Quantumsort werkt op bijna exact dezelfde manier als Bogosort, maar in plaats van de gegevens willekeurig te husselen totdat de lijst gesorteerd is, gebeurt dat maar één keer. Als de lijst daarna niet gesorteerd is, zit er niets anders op dan je eigen universum te laten vernietigen.
Het uitgangspunt daarbij is dat de gebeurtenis van ‘één keer husselen’ op kwantumniveau een enorm aantal mogelijke uitkomsten creëert die naast elkaar bestaan in parallelle universa totdat het resultaat bepaald is (hallo Schrödinger).
Door vervolgens alle universa waarin de items in de verkeerde volgorde staan te vernietigen, blijft alleen het parallelle universum met de juiste uitkomst over, zodat de lijst meteen correct is gesorteerd.
Omdat we vrezen dat we misschien niet in het overblijvende parallelle universum met de juiste sorteervolgorde zullen zitten, en omdat de vrij essentiële functie om het universum anders te vernietigen nog door niemand lijkt te zijn gerealiseerd, hebben we besloten om Quantum-Bogosort maar niet te implementeren.
Miraclesort
Een andere klassieker is Miraclesort. Ruim 15 jaar geleden onthulde programmeur Keith Thompson die methode in een Stack Overflow-thread als antwoord op de vraag of er slechtere sorteeralgoritmes waren dan Bogosort. In de afbeelding zie je hoe Miraclesort er als pseudocode uitziet.
In principe wacht Miraclesort tot de lijst plotseling door een wonder gesorteerd is. In zijn antwoord zelf formuleert Thompson dat alfadeeltjes op een gegeven moment genoeg bits in het geheugen zouden kunnen omdraaien om de lijst te sorteren. Hij benadrukt echter dat Miraclesort strikt genomen geen algoritme is omdat er geen garantie is dat het ooit eindigt.
Sleepsort
Het laatste algoritme uit de categorie klassiekers dat we aan je willen voorstellen is Sleepsort. Dat algoritme geniet in sommige kringen een zekere reputatie, die te danken is aan het feit dat Sleepsort in 2011 het levenslicht zag op het internetplatform 4chan.
Het Sleepsort-algoritme, beschreven door een anonieme gebruiker, mag je niet verwarren met het gelijknamige sorteeralgoritme uit 1986. Dat werd door Jonathan Traugott geformuleerd als een parodie op Mergesort in het paper Deductive synthesis of sorting programs.
Sleepsort van 4chan gebruikt een revolutionaire manier om getallen te sorteren. Er zijn geen verwisseloperaties nodig zoals bij Bubblesort, geen invoegoperaties zoals bij Insertionsort, geen slimme procedures of trucs zoals bij Quicksort en Timsort. Nee, het proces sorteert de lijst letterlijk slapend en maakt gebruik van het tegenwoordig gangbare multitasking.
def sleepsort(a):
result = []
threads = [threading.Thread(
target=sleeper, args=(n, result) ) for n in a]
[t.start() for t in threads]
[t.join() for t in threads]
return resultdef sleeper(n, result):
time.sleep(n)
result.append(n)Het programma maakt voor elk getal n uit a een aparte thread aan, die n seconden slaapt voordat hij n teruggeeft. Sleepsort spuugt uiteindelijk de getallen uit in de volgorde waarin de threads wakker worden. Het sorteeralgoritme is niet stabiel en heeft een ongelooflijk lange looptijd, die afhangt van de grootte van de getallen – namelijk minstens max(a) seconden.
De tijd totdat het resultaat beschikbaar is kun je natuurlijk wel voor andere dingen gebruiken …
Permatationsoft
Bij de beslissing welk sorteeralgoritme te gebruiken, speelt de runtime O een belangrijke rol. Niemand wil immers eeuwig wachten op een resultaat – daarom is Sleepsort niet geschikt voor (oneindig) grote getallen.
Permutationsort, waarbij eerst alle mogelijke volgordes van de te sorteren waarden worden opgesteld en vervolgens wordt gezocht naar de volgorde waarin de waarden gesorteerd zijn, moet dienen als voorbeeld voor het bepalen van de runtime. In tegenstelling tot Bogosort probeert Permutationsort specifiek alle mogelijkheden uit, zodat geen enkele reeks toevallig twee keer kan voorkomen.
Er wordt ook geen reeks overgeslagen omdat het resultaat al gevonden is. Dat maakt het eenvoudig om de runtime te bepalen, die met Permutationsort altijd gegarandeerd O(n! – n) is.
Geïmplementeerd in Python zou die maximale verspilling van resources er als volgt uitzien:
def permutationsort(a):
p = list(permutations(a))
for perm in p:
if check_if_sorted(perm):
return permDe lijst met alle permutaties wordt gegenereerd door de functie permutations() uit de geïmporteerde bibliotheek itertools. Je hebt check_if_ sorted() al gezien bij Bogosort.
Met Bogosort hangt het echter van het toeval af hoe lang het algoritme duurt. In het ideale geval is de eerste reeks al perfect gesorteerd, wat zou overeenkomen met O(1). Normaliter duurt het echter vrij lang tot de juiste volgorde gevonden is, zodat we gemiddeld O(n!/2) kunnen aannemen.
In het ergste geval duurt het echter oneindig lang, namelijk als Bogosort niet toevallig de juiste volgorde vindt.
Stalinsort
Een bijzonder snel algoritme vergeleken met Bogosort en vooral Permutationsort is Stalinsort. Het maakt niet uit hoeveel items het moet verwerken of hoe ongeordend die zijn aan het begin, Stalinsort heeft altijd een gegarandeerde runtime van O(n). Hoe kan dat?
De manier waarop dat niet erg subtiele proces werkt kan in één zin worden samengevat: iedereen die buiten de lijntjes kleurt wordt geëlimineerd. Vertaald in de taal van sorteeralgoritmes: het proces doorloopt de lijst die gesorteerd moet worden precies één keer en controleert voor elke waarde of de volgende waarde groter of gelijk is aan die waarde. Zo ja, dan gaat het verder met de volgende waarde; zo nee, dan wordt die volgende waarde uit de lijst verwijderd.
Het resultaat is dat daarna alle waarden netjes in oplopende volgorde staan – al zullen er misschien een (flink) aantal zijn weggevallen.
In Python ziet Stalinsort er als volgt uit:
def stalinsort(a):
result = []
max = a[0]
for n in range (len(a) ) :
if a[n] >= max :
result . append(a[n])
max = a[n]
return resultIn onze voorbeeldcode elimineert Stalinsort niet eens alle getallen die niet op volgorde staan, maar onthoudt gewoon enkel de waarden die groter of gelijk zijn aan de vorige grootste waarde max.
Er is zelfs een populaire GitHub-repository genaamd Stalin-Sort met meer dan 1700 sterren, waar men Stalinsort deelt in tientallen programmeertalen (zie de link).
Voor sommige populaire programmeertalen zijn er verschillende absurd complexe implementaties van Stalinsort.
Er zijn niet alleen implementaties te vinden in bekende talen zoals Python, Java en C, maar ook in esoterische programmeertalen zoals Brainfuck en Whitespace. De eerste bestaat alleen uit de tekens <>+-.,[] en ziet er daarom, niet verrassend, afschuwelijk uit.
Whitespace is esthetisch verantwoorder omdat de instructies alleen uit spaties en regeleinden bestaan. Dat is zelfs milieuvriendelijk bij het afdrukken van de code omdat het toner- en inktverbruik tot een minimum beperkt wordt.
Omdat Whitespace nauwelijks geschikt is als voorbeeld in een artikel dat (ook) door mensenogen wordt bekeken, kun je in plaats daarvan hieronder Stalinsort in Brainfuck bewonderen, zoals GitHub-gebruiker nfd9001 het heeft gepubliceerd op GitHub:
,.[->+>+<<],[[->>>+>+<<<<]>>>>>[-]>[-]>[-]+>[-]<<<<<[>>+>+<<<-]>>>[<<<+>>>-]<<<<[>>>>+<<<<-]>>>>[>-]>[<<<<<+>>>[-]>>->]<+<<[>-[>-]>[<<<<<+>>>[-]+>>->]<+<<-][-]>[-]<<<<[>>>+>+<<<<-]>>>[<<<+>>>-]+>[<<.<[-]<[-]<[-]>>>[-<<+<+>>>]>->[-]]<[<[-]<[-]<<[-<+>]<[->+>+<<]>>>>>-]<<<<<,]Nihilistsort
Nog sneller dan Stalinsort is Nihilistsort, ook bekend als Voidsort. Dat programma – dat het niet langer verdient om een sorteeralgoritme genoemd te worden – heeft als enige bewerking dat het de lijst verwijdert. Waar niets is, hoeft ook niets gesorteerd te worden. De gegarandeerde runtime is daarom O(1).
def nihilistsort (a):
return NoneNihilistsort is een goede overgang naar de categorie sorteeralgoritmes die alleen een spitsvondige naam hebben en niet eens proberen om gegevens te sorteren.
Er zijn er inmiddels zoveel dat het niet mogelijk is om die monsterlijke verzameling te publiceren – daarom noemen we hier alleen onze favorieten.
Malgoritmes
Toen de afsluiting van de Infinity-saga in het Marvel Cinematic Universe een paar jaar geleden in de bioscopen verscheen met de films Avengers: Infinity War en Avengers: Endgame, deed het sorteeralgoritme Thanossort de ronde. Er zijn verschillende implementaties van Thanossort, maar ze verwijderen allemaal de helft van de waarden die gesorteerd moeten worden om de balans in het universum te herstellen.
Een ander voorbeeld van een sorteeralgoritme dat niets goed doet is Trumpsort. Het verscheen op forums aan het begin van de eerste ambtstermijn van de huidige Amerikaanse president en steekt de draak met het bestempelen van alles als fake news dat niet overeenkomt met de eigen mening.
Trumpsort zal de waarden in een lijst dus willekeurig door elkaar gooien, om vervolgens te beweren dat die daarna gesorteerd is. Iedereen die iets anders beweert, verspreidt fake news.
We hebben ook twee mogelijke implementaties van Schrödingersort gevonden. De eerste variant husselt de lijst willekeurig, zoals bij Bogosort, maar slechts één keer en slaat het resultaat op in een tekstbestand met de naam Niet openen!. De lijst is dan, zogenaamd volgens de wetten van de kwantumfysica, zowel gesorteerd als ongesorteerd – zolang je het tekstbestand niet opent en een kijkje neemt.
De tweede variant gaat dezelfde kant op. Die voert eerst een paar willekeurige bewerkingen uit op de lijst en versleutelt daarna het resultaat. Zolang je het bestand niet ontsleutelt, zie Schrödinger.
Intelligent Design Sort volgt een soortgelijke logica als Trumpsort. Dat algoritme gaat ervan uit dat de lijst die gesorteerd moet worden is aangeleverd door een intelligente schepper en daarom al gesorteerd is op een manier die mensen met hun beperkte geest niet kunnen bevatten.
Die lijst mag daarom onder geen beding worden veranderd, omdat dat de goddelijke orde zou verstoren. De procedure is bedacht door de Australische natuurkundige David Morgan-Mar en gepubliceerd op zijn website dangermouse.net, waar nog veel meer sorteeralgoritmes en esoterische programmeertalen te vinden zijn.
Genoeg gesorteerd
Genoeg gehusseld, hiermee eindigen we onze artikelreeks over de wereld van sorteeralgoritmes. In het volgende magazine en op de website staat à la Schrödinger wel of geen vervolg op dit artikel – totdat je daar kijkt. Je mag best een berichtje sturen welke algoritmes daar niet mogen ontbreken.
Wilhelm Drehling en Marco den Teuling
Literatuur
[1] Wilhelm Drehling en Marco den Teuling, Sorteeralgoritmes: zo werken Bubblesort, Quicksort en Mergesort, c’t 6/2027, p.108
[2] Wilhelm Drehling en Marco den Teuling, Sorteeralgoritmes: waarom Timsort zo snel is, c’t 7/2026, p.108
Praat mee