Tot nu toe bekeken we het Random Sort algoritme als oplossing voor het sorteerprobleem. Er zijn echter nog vele andere manieren waarop een willekeurige lijst van klein naar groot gesorteerd kan worden.
👀 Voorbeeld – Leerlingen sorteren 2
We kijken opnieuw naar de rij van leerlingen, maar nu zijn er 2 leerlingen ziek. Niet alle klasnummers zijn dus aanwezig. De leerkracht gebruikt nu een andere, slimmere aanpak:
- De leerkracht vraagt aan de leerlingen in de rij wie het kleinste klasnummer heeft.
- Deze leerling wisselt van plaats met de leerling vooraan in de rij en gaat op de grond zitten.
- Dan vraagt de leerkracht aan alle rechtstaande leerlingen wie nu het laagste klasnummer heeft.
- Deze leerling wisselt van plaats met de eerste leerling in de rij die nog rechtstaat en gaat op de grond zitten.
- Dit gaat door totdat alle leerlingen op de grond zitten.
❗ Begrip – Selection Sort
Een tweede, efficiëntere manier om een lijst te sorteren is aan de hand van het Selection Sort algoritme. Dit gaat als volgt:
- De lijst bevat nog geen gesorteerd deel. Ze vormt in zijn geheel het ongesorteerde deel.
- Zoek in het ongesorteerde deel van de lijst naar het kleinste element.
- Wissel dit gevonden kleinste element van plaats met het eerste element in het ongesorteerde deel.
- Dit kleinste element is nu gesorteerd en behoort tot het gesorteerde deel.
- Stop als het ongesorteerde deel leeg is. Ga anders terug naar stap 2.
🧠 Denkoefening – Efficiënter sorteren: Selection Sort
Voer het Selection Sort algoritme nu uit op de lijst
[20, 40, 10, 30].
- Welk element wordt gevonden als stap 3 voor de eerste keer wordt uitgevoerd?
- Hoe ziet de lijst eruit na stap 3 voor de eerste keer?
- Welk element wordt gevonden als stap 3 voor de tweede keer wordt uitgevoerd?
- Hoe ziet de lijst eruit na stap 3 voor de tweede keer?
- Welk element wordt gevonden als stap 3 voor de derde keer wordt uitgevoerd?
- Hoe ziet de lijst eruit na stap 3 voor de derde keer?
Om Selection Sort te implementeren, moeten we eerst weten hoe we de index van het kleinste element uit (een deel van) een lijst kunnen terugvinden.