Hiervoor bespraken we het Random Sort en Selection Sort algoritme. Selection Sort volbracht de taak op een efficiëntere manier dan Random Sort. Nu bekijken we een derde algoritme.

Bij Selection Sort was de lijst steeds opgesplitst in twee delen: het gesorteerde deel en het ongesorteerde deel. We vergrootten het gesorteerde deel één per één door telkens het kleinste element uit het ongesorteerde deel te zoeken. We zochten dus naar het volgende element voor het gesorteerde deel.

Er is ook een alternatief: zoeken naar waar het volgende element van het ongesorteerde deel geplaatst moet worden in het gesorteerde deel. Dit is precies wat Insertion Sort doet.

👀 Voorbeeld - Leerlingen sorteren

De leerkracht lost het sorteervraagstuk nu op een derde manier op: dit noemen we insertion sort. Het idee lijkt sterk op hoe je zelf vaak dingen ordent in het dagelijks leven, zoals een rij leerlingen op klasnummer of een stapel kaarten in de juiste volgorde.

De leerkracht vraagt alle leerlingen om te gaan zitten. Er zijn dus nog geen rechtstaande leerlingen.
👉 Belangrijk: een zittende leerling is “nog niet in de gesorteerde rij”.

De leerkracht vraagt aan de voorste zittende leerling om op te staan en zich in de juiste positie te plaatsen in de rij van rechtstaande leerlingen.
👉 In het begin is die rij nog leeg, dus de eerste leerling mag gewoon meteen rechtstaan.

Vanaf nu bouwen we de gesorteerde rij stap voor stap op:

De net rechtgestane leerling kijkt naar de leerlingen die al rechtstaan.

Hij of zij vergelijkt zichzelf met de leerling direct ervoor.

Zolang de nieuwe leerling niet helemaal vooraan staat én een lager klasnummer heeft dan de leerling ervoor, wisselen ze van plaats.
👉 Dit heet “naar links schuiven tot je op je juiste plaats zit”.

Als de leerling op zijn juiste plaats staat, blijft die staan.
Daarna wordt de volgende zittende leerling gevraagd om op te staan en stap 2 herhaalt zich.

Dit proces gaat door totdat alle leerlingen rechtstaan.
👉 Op dat moment is de volledige rij gesorteerd.

💡 Intuïtief idee: je bouwt een gesorteerde rij van links naar rechts op, en elke nieuwe leerling wordt meteen “ingevoegd” op de juiste plek in het reeds gesorteerde deel.

❗ Begrip – Insertion Sort

Een derde manier om een lijst te sorteren is aan de hand van het Insertion Sort algoritme. Dit gaat als volgt:

De lijst is nog niet gesorteerd.

Bekijk het eerste element van het ongesorteerde deel.

Zolang dit element niet vooraan staat en kleiner is dan het element ervoor, wissel je het van plaats met het element ervoor.

Als het ongesorteerde deel leeg is, stop. Keer anders terug naar stap 2.

🧠 Denkoefening – Efficiënter sorteren: Insertion Sort

Voer het Insertion Sort algoritme nu uit op de lijst [40, 20, 10, 30].

Hoe ziet de lijst eruit nadat stap 3 voor de eerste keer is uitgevoerd?

Hoe ziet de lijst eruit nadat stap 3 voor de tweede keer is uitgevoerd?

Hoe ziet de lijst eruit nadat stap 3 voor de derde keer is uitgevoerd?

Hoe ziet de lijst eruit nadat stap 3 voor de vierde keer is uitgevoerd?