Je klastitularis wilt de 20 leerlingen van je klas sorteren van klein naar groot. Hij/zij zou dit op volgende gestructureerde manier kunnen aanpakken:
In het begin staan alle leerlingen in één rij, willekeurig door elkaar.
De klastitularis beschouwt de eerste leerling als een aparte, gesorteerde groep. Je hebt nu een groep van 1 leerling die gesorteerd is, en een groep van 19 leerlingen die niet gesorteerd is.
De klastitularis kijkt naar de eerste leerling uit het ongeordende deel van de lijst. Deze heeft index 1. De klastitularis vergelijkt deze leerling met de leerlingen in het geordende deel. Er zijn nu twee mogelijkheden:
De leerling met index 1 is kleiner dan de leerling op index 0. In dat geval wisselen beide van plaats. De leerling die op index 0 stond, komt naar achter. De leerling die index 1 had, komt nu helemaal vooraan te staan.
De leerling met index 1 is niet kleiner dan de leerling op index 0. De nieuwe leerling blijft gewoon op index 1 staan.
Je hebt nu een groep van 2 leerlingen die geordend is, en een groep van 18 leerlingen die ongeordend is.
De klastitularis kijkt opnieuw naar de eerste leerling uit het ongeordende deel van de lijst. Deze heeft index 2. De klastitularis vergelijkt deze leerling met de leerlingen in het geordende deel. Hij/zij schuift deze leerling naar de juiste plaats. Dat gebeurt door herhaaldelijk naast elkaar staande leerlingen van plaats te wisselen, totdat de juiste positie gevonden is. Je hebt nu een groep van 3 leerlingen die geordend is, en een groep van 17 leerlingen die ongeordend is.
…
De klastitularis blijft verder werken tot het ongeordende deel van de groep leeg is. Op dat moment zitten er 20 leerlingen in het geordende deel van de groep. De klasgroep is nu gesorteerd van klein naar groot.
Deze strategie wordt Insertion sort genoemd. Net zoals bij Selection sort wordt ook nu de lijst opgesplitst in twee delen, het gesorteerde deel en het nog niet-gesorteerde deel. Het gesorteerde deel wordt gaandeweg vergroot door telkens het eerste element uit het niet-gesorteerde deel te nemen en het op de juiste plaats in het gesorteerde deel in te voegen. We voegen dus herhaaldelijk een element in op de correcte positie, waarbij de al gesorteerde elementen opschuiven om plaats te maken.
In het begin is de lijst niet gesorteerd.
Neem het element op index 0 en voeg het in op de juiste plaats in de gesorteerde deellijst (die op dit moment nog leeg is). Het element blijft dus op index 0 staan. De deellijst lijst[:1] is nu gesorteerd. De deellijst lijst[1:] is nog niet gesorteerd.
Neem het element op index 1 en vergelijk het van rechts naar links met de elementen in de gesorteerde deellijst. Elementen die groter zijn schuiven één plaats naar rechts, totdat de juiste positie gevonden is. Voeg het element in op die positie. De deellijst lijst[:2] is nu gesorteerd. De deellijst lijst[2:] is nog niet gesorteerd.
Neem het element op index 2 en vergelijk het van rechts naar links met de elementen in de gesorteerde deellijst. Elementen die groter zijn schuiven één plaats naar rechts, totdat de juiste positie gevonden is. Voeg het element in op die positie. De deellijst lijst[:3] is nu gesorteerd. De deellijst lijst[3:] is nog niet gesorteerd.
Blijf deze stappen herhalen tot de niet-gesorteerde deellijst leeg is. Op dat moment bevat de gesorteerde deellijst alle elementen van lijst. lijst is dus gesorteerd.
Pas bovenstaand stappenplan toe op de lijst [9, -5, 8, -3, -10, 4, 5]. Noteer alle tussenstappen om tot een gesorteerde lijst te komen.
1) 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.
2) Schrijf een functie insertion_sort(lijst). lijst is een lijst met getallen. Je functie past het bovenstaande stappenplan toe en geeft de gesorteerde versie van lijst terug.
Invoer:
> wissel_elementen([-10, -5, 9, 8, -3, 4, 5], 2, 3)
Uitvoer:
[-10, -5, 8, 9, -3, 4, 5]
Invoer:
> insertion_sort([9, -5, 8, -3, -10, 4, 5])
Uitvoer:
[-10, -5, -3, 4, 5, 8, 9]