Je klastitularis wilt de 20 leerlingen van je klas sorteren van klein naar groot. In het begin staan alle leerlingen in één rij, willekeurig door elkaar. Hij/zij zou dit op volgende gestructureerde manier kunnen aanpakken:
0) De klastitularis overloopt alle leerlingen en zoekt naar de kleinste leerling. Deze wisselt van plaats met het element met index 0, en komt dus helemaal vooraan te staan. Je hebt nu een deelgroep (van 1 leerling) die geordend is, en een deelgroep van 19 leerlingen die ongeordend is.
1) De klastitularis overloopt alle leerlingen en zoekt naar de kleinste leerling in het ongeordende deel van de groep (19 personen). Deze wisselt van plaats met het element met index 1, en komt dus achter het reeds geordende deel van de groep te staan. Je hebt nu een deelgroep van 2 leerlingen die geordend is, en een deelgroep van 18 leerlingen die ongeordend is.
2) De klastitularis overloopt alle leerlingen en zoekt naar de kleinste leerling in het ongeordende deel van de groep (18 personen). Deze wisselt van plaats met het element met index 2, en komt dus achter het reeds geordende deel van de groep te staan. Je hebt nu een deelgroep van 3 leerlingen die geordend is, en een deelgroep van 17 leerlingen die ongeordend is.
3) …
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 Selection sort genoemd. De idee is dat je herhaaldelijk een element selecteert en het vervolgens op de gewenste plaats in de lijst zet.
In het begin is de lijst niet gesorteerd.
0) Overloop alle elementen van de lijst, te beginnen bij index 0. Zoek naar het kleinste element en wissel dit van plaats met het element op index 0. De deellijst lijst[:1] is nu gesorteerd. De deellijst lijst[1:] is nog niet gesorteerd.
1) Overloop alle elementen van de lijst, te beginnen bij index 1. Zoek naar het kleinste element en wissel dit van plaats met het element op index 1. De deellijst lijst[:2] is nu gesorteerd. De deellijst lijst[2:] is nog niet gesorteerd.
2) Overloop alle elementen van de lijst, te beginnen bij index 2. Zoek naar het kleinste element en wissel dit van plaats met het element op index 2. De deellijst lijst[:3] is nu gesorteerd. De deellijst lijst[3:] is nog niet gesorteerd.
3) Blijf deze stappen overlopen 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 zoek_kleinste(lijst, start). lijst is een lijst met getallen. start is een natuurlijk getal dat verwijst naar de index van een element. Je functie overloopt alle getallen in het deel van de lijst dat begint bij de index start. Je functie geeft een tuple terug met twee elementen:
de waarde van het kleinste element in dit deel van de lijst;
de index van het kleinste element in dit deel van de lijst.
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 selection_sort(lijst). lijst is een lijst met getallen. Je functie past het bovenstaande stappenplan toe en geeft de gesorteerde versie van lijst terug.
Invoer:
> zoek_kleinste([-10, -5, 9, 8, -3, 4, 5], 2)
Uitvoer:
(-3, 4)
Invoer:
> wissel_elementen([-4, 5, -1, 0, -4], 1, 4)
Uitvoer:
[-4, -4, -1, 0, 5]
Invoer:
> selection_sort([9, -5, 8, -3, -10, 4, 5])
Uitvoer:
[-10, -5, -3, 4, 5, 8, 9]