Stellingen — toets je begrip
Leerdoel: je toetst of je het idee van steeds-de-kleinste-vooraan snapt, voordat je gaat programmeren.
Stelling 1
"Selection sort sorteert de lijst van laag naar hoog door elke ronde de grootste vooraan te zetten."
Antwoord
Onjuist. Bij sorteren van laag naar hoog zet je het kleinste vooraan; de grootste komt vanzelf achteraan terecht.
Andersom kan ook: zet je elke ronde de grootste vooraan, dan sorteer je van hoog naar laag. Daar oefen je mee bij Aanpassen.
Stelling 2
"Na ronde k staan de eerste k elementen op hun juiste plek."
Antwoord
Juist. Dat heet de invariant van selection sort: het gesorteerde
stuk vooraan groeit elke ronde met één element. Daar heb je iets aan, want
in ronde k hoef je alleen nog naar de rest te kijken, vanaf index k.
Stelling 3
"Selection sort doet altijd evenveel vergelijkingen, ook als de lijst al gesorteerd is."
Antwoord
Juist. Het algoritme zoekt in elke ronde door het hele ongesorteerde
stuk, ongeacht wat het al gevonden heeft. Op een al-gesorteerde lijst zijn
het nog steeds n(n + 1)/2 vergelijkingen.
Bubble sort, het volgende hoofdstuk, kan dat wél merken en eerder stoppen.
Stelling 4
"Bij selection sort gebeurt er één swap per ronde."
Antwoord
Juist. In elke ronde wordt het kleinste element gevonden en op zijn
plek geruild: precies één swap-regel per ronde. Vaak ruilt die regel een
element met zichzelf, want het kleinste stond al vooraan; dan verandert er
niets. In de laatste ronde gebeurt dat altijd, want er is nog maar één
element over. Er verhuizen dus hoogstens n − 1 elementen echt: veel
vergelijkingen, weinig verplaatsingen.
Dat is een voordeel wanneer verplaatsen duur is, bijvoorbeeld als de elementen grote objecten zijn.
Stelling 5
"Als je in de eerste ronde het kleinste vindt op positie 3, dan moeten ook posities 0, 1 en 2 worden verschoven."
Antwoord
Onjuist. Selection sort ruilt alleen, het schuift niet. Het element op positie 3 wisselt van plek met dat op positie 0; de elementen op 1 en 2 blijven waar ze zijn.
Stelling 6
"Selection sort sorteert in plaats — je hebt geen tweede lijst nodig."
Antwoord
Juist. Het algoritme verandert de oorspronkelijke lijst zelf, zonder kopie. Bij grote hoeveelheden data scheelt dat geheugen.
Wil je de oorspronkelijke lijst houden, sorteer dan een kopie:
gesorteerd = selection_sort(lijst.copy()).
Door naar de eerste bouwsteen.