Stellingen — toets je begrip
Leerdoel: je toetst of je de structuur van bubble sort snapt.
Stelling 1
"Eén pass van bubble sort sorteert de hele lijst."
Antwoord
Onjuist. Eén pass zet alleen het grootste element op zijn plek, achteraan het ongesorteerde stuk. De rest kan nog door elkaar staan, dus er komen meer passes achteraan.
Stelling 2
"Na pass k staan de laatste k elementen op hun juiste plek."
Antwoord
Juist. Elke pass borrelt de grootste van de rest naar achteren: na pass 1 staat het grootste goed, na pass 2 ook het tweede grootste, en zo verder.
Daar maak je straks gebruik van: elke volgende pass hoeft een stukje minder ver te kijken, want de staart staat al.
Stelling 3
"Bubble sort vergelijkt alleen buren (lijst[i] met lijst[i+1])."
Antwoord
Juist. Dat is het kenmerk van bubble sort. Selection sort vergelijkt elk element met de kleinste tot nu toe, en die kan ver weg staan; bubble sort kijkt alleen naar wat naast elkaar ligt.
Dat maakt de logica simpel, maar het kost tijd: een element dat ver van zijn plek staat schuift per pass maar één positie op.
Stelling 4
"Op een al-gesorteerde lijst kan bubble sort na één pass stoppen."
Antwoord
Juist. Die ene pass vergelijkt elk paar buren en wisselt niets. Dan
weet je zeker dat de lijst af is, en hoef je niet verder. Dat "merken dat
er niets gewisseld is" bouw je in bouwsteen 5; zonder die stap doet
bubble sort ook op een gesorteerde lijst alle n − 1 passes.
Stelling 5
"De binnenste lus loopt tot len(lijst) (inclusief)."
Antwoord
Onjuist. Hij loopt tot len(lijst) - 1. Je vergelijkt lijst[i] met
lijst[i+1], dus de laatste i die nog kan is len(lijst) - 2, en dat
is precies wat range(len(lijst) - 1) je geeft.
Eén te ver → IndexError op lijst[i+1].
Stelling 6
"Bubble sort kan elementen die ver van hun juiste plek staan ook in één pass naar voren brengen."
Antwoord
Onjuist, tenminste naar voren. Een kleine waarde schuift per pass maar één plek op; een grote kan in één pass helemaal naar achteren bubbelen.
Die scheefheid is precies wat cocktail sort rechttrekt, door om en om naar rechts en naar links te lopen.
Door naar de eerste bouwsteen.