Selection sort — het idee

Leerdoel: je begrijpt hoe selection sort werkt: telkens het kleinste element vinden en vooraan zetten. Nog geen Python — eerst snappen.

Het verhaal

Je hebt een stapel speelkaarten op tafel liggen, door elkaar, en je wilt ze van laag naar hoog sorteren.

Zo pak je dat met de hand aan:

1. Zoek in de hele stapel de laagste kaart en leg die links neer.
2. Zoek de laagste van wat er nog ligt en leg die ernaast.
3. Daarna de laagste van de rest, en die legt zich weer ernaast.
4. Net zo lang tot je niets meer over hebt.

Dat is selection sort in één zin: kies steeds het kleinste van de rest en zet het vooraan.

Visualisatie

We sorteren [5, 2, 8, 1, 4]. De elementen tussen haakjes staan al op hun juiste plek.

start:    [ 5 , 2 , 8 , 1 , 4 ]     vind kleinste in [5,2,8,1,4] → 1 (op index 3)
swap 0↔3: [(1), 2 , 8 , 5 , 4 ]     1 staat goed (tussen haakjes)

stap 2:   [ 1 |  2 , 8 , 5 , 4 ]    vind kleinste in [2,8,5,4] → 2 (op index 1)
swap 1↔1: [(1)|(2), 8 , 5 , 4 ]     2 staat al goed (swap met zichzelf)

stap 3:   [ 1 , 2 |  8 , 5 , 4 ]    vind kleinste in [8,5,4] → 4 (op index 4)
swap 2↔4: [(1)|(2)|(4), 5 , 8 ]     4 staat goed

stap 4:   [ 1 , 2 , 4 |  5 , 8 ]    vind kleinste in [5,8] → 5 (op index 3)
swap 3↔3: [(1)|(2)|(4)|(5), 8 ]     5 staat al goed

stap 5:   [ 1 , 2 , 4 , 5 |  8 ]    nog 1 over, dus klaar
eind:     [ 1 , 2 , 4 , 5 , 8 ]

Het idee in stappen

Twee dingen die je per ronde doet:

1. Zoek het kleinste in het deel van de lijst dat nog niet gesorteerd is. Dat is het vind-minimum-algoritme dat je kent, alleen niet over de hele lijst maar over een stuk ervan.
2. Ruil dat kleinste element met het element op positie i, de eerste plek van het ongesorteerde deel.

Herhaal voor i = 0, 1, 2, … tot je bij het laatste element bent.

Twee bouwstenen die je herkent

• Het minimum zoeken gaat met het accumulator-patroon dat je kent van vind het maximum. Nu zoek je de index van het kleinste, en niet in de hele lijst maar in het stuk dat nog ongesorteerd is.
• Swappen is twee elementen van plaats laten ruilen. In Python is dat één regel: a, b = b, a.

Hoe snel is dit?

Voor n elementen doe je:

• Ronde 1 zoekt het kleinste in n elementen en doet n vergelijkingen.
• Ronde 2 zoekt in n − 1 elementen en doet er n − 1.
• …
• In ronde n is er nog één element over: één vergelijking.

Totaal: 1 + 2 + … + n = n(n + 1) / 2 ≈ O(n²).

Dat elke ronde één vergelijking meer doet dan je zou verwachten, komt doordat de zoektocht begint bij het element dat al vooraan staat: dat wordt één keer met zichzelf vergeleken. Voor 1.000 elementen zijn het er ruim 500.000, voor 10.000 elementen ruim 50.000.000. Selection sort is dus langzaam voor grote lijsten, maar simpel om te begrijpen, en daarom een mooie eerste sorteer.

info

De stapel speelkaarten uit het verhaal kun je echt op tafel leggen: zie de werkvorm in Zoeken en sorteren met kaarten.

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

1. Bouwsteen 1 — vind de index van het kleinste
2. Bouwsteen 2 — twee elementen ruilen
3. Bouwsteen 3 — zoek vanaf een bepaalde positie
4. Bouwsteen 4 — de bouwstenen aan elkaar rijgen

Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.

Door naar bekijk het algoritme.