Beeld je in dat je een spel kaarten wilt sorteren. Een extreem inefficiënte manier zou kunnen zijn om dat als volgt te doen:
1) Controleer of de kaarten gesorteerd zijn. Als dat niet het geval is, ga je verder met stap 2. Als dat wel het geval is, ga je verder met stap 3.
2) Verwissel twee willekeurige kaarten van plaats. Ga terug naar stap 1.
3) Proficiat: de kaarten zijn gesorteerd!
Deze strategie wordt Random sort genoemd. Als praktisch sorteeralgoritme heeft deze strategie geen enkele waarde. Er is immers geen enkele garantie dat dit algoritme altijd tot het gewenste resultaat zal leiden. Als dit algoritme al tot een resultaat leidt, zal het naar verwachting ook bijzonder lang duren in vergelijking met andere algoritmes. De enige verdienste die dit algoritme heeft, is de didactische waarde: het algoritme is gemakkelijk te begrijpen en te implementeren.
1) Schrijf een functie is_gesorteerd(lijst). lijst is een lijst met getallen. Je functie geeft True terug als lijst gesorteerd is van klein naar groot, en False wanneer dat niet het geval is.
2) Schrijf een functie wissel_elementen(lijst, index_1, index_2). lijst is een lijst met getallen. index_1 en index_2 zijn natuurlijke getallen die verwijzen naar de index van twee elementen in de lijst. Je functie geeft de lijst terug waarin de elementen op index_1 en index_2 van plaats verwisseld zijn.
3) Schrijf een functie random_sort(lijst). lijst is een lijst met getallen. Je functie gaat herhaaldelijk twee willekeurige elementen van lijst omwisselen. Je stopt hier pas mee wanneer lijst gesorteerd is. Je functie geeft de gesorteerde versie terug van lijst. Uiteraard maak je hierbij gebruik van de functies is_gesorteerd(lijst) en wissel_elementen(lijst, index_1, index_2) die je net geïmplementeerd hebt.
Invoer:
> is_gesorteerd([1, 2, 3, 4])
Uitvoer:
True
Invoer:
> is_gesorteerd([1, 4, 2, 3])
Uitvoer:
False
Invoer:
> wissel_elementen([1, 2, 3, 4], 2, 3)
Uitvoer:
[1, 2, 4, 3]
Invoer:
> random_sort([1, 4, 2, 3])
Uitvoer:
[1, 2, 3, 4]