Af en toe is het handig om een rij van getallen te sorteren van klein naar groot. Eén manier om dit te doen is door het Random Sort algoritme te gebruiken.
Door herhaaldelijk willekeurige getallen van plaats te verwisselen in de rij, bekomt dit algoritme uiteindelijk — wonder boven wonder — toch een rij met getallen gerangschikt van klein naar groot!
👀 Voorbeeld – Leerlingen sorteren
De leerkracht van het 6e jaar wil graag dat de leerlingen op één lange rij gaan staan op basis van hun klasnummer. De leerlingen staan echter nog na te babbelen en staan momenteel in een willekeurige volgorde. Daarom doet de leerkracht het volgende:
- Elke 10 seconden trekt de leerkracht blind twee willekeurige nummers uit een zak.
- De twee leerlingen die op deze plaatsen staan in de rij moeten dan van plaats wisselen.
- De leerkracht stopt dan beide nummers weer in de zak zodat ze opnieuw getrokken kunnen worden.
Als de leerkracht bijvoorbeeld de nummers 1 en 5 uit de zak trekt, moeten de leerlingen op de 2e en de 6e plaats in de rij van plaats wisselen. (Het cijfertje 0 zit ook in de zak en staat voor de eerste leerling.)
Totdat de leerlingen op de juiste volgorde staan, blijft de leerkracht nummertjes trekken.
Misschien heb je al door dat dit niet echt de beste manier is om de leerlingen te sorteren…
❗ Begrip – Random Sort
Eén van de makkelijkste (en minst efficiënte) manieren om een lijst te sorteren gaat als volgt:
- Kijk na of de lijst volledig gesorteerd is.
- Indien niet gesorteerd, ga naar stap 3. Indien wel gesorteerd, stop.
- Wissel de waarden van de elementen op 2 willekeurige posities van plaats. Keer hierna terug naar stap 1.
Voor het Random Sort algoritme zijn twee willekeurige geldige indexen nodig:
- indexen groter dan of gelijk aan 0 (de
-1e plaats bestaat niet) - indexen die niet te groot zijn voor de gegeven lijst
👀 Voorbeeld – Geldige en ongeldige indexen
Voor de lijst
[0, 1, 2, 3, 4, 5]zijn dit geldige resultaten:
(0, 1)✅(2, 4)✅En dit zijn ongeldige resultaten:
(-1, 3)❌ —-1is geen geldige index[0, 1]❌ — we willen een tupel, geen lijst(10, 3)❌ — index10bestaat niet in een lijst van 6 elementen