Ga naar hoofdinhoud

Bouwsteen 2 — twee buren ruilen

Hier bouw je op verder

Leerdoel: je kunt twee opeenvolgende elementen ruilen wanneer ze fout staan.

Wat we willen​

Bij elk paar dat fout staat (lijst[i] > lijst[i+1]): de twee elementen omwisselen.

Eén regel: tuple-swap​

Net als bij selection sort gebruiken we de Pythonische tuple-swap:

lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]

Python evalueert eerst de rechterkant tot een tuple (lijst[i+1], lijst[i]) en kent die dan toe aan de linkerkant. Geen informatieverlies.

Voorspel​

Wat denk je dat dit print?

lijst = [3, 1, 4, 1, 5]
i = 0

if lijst[i] > lijst[i + 1]:
    lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]

print(lijst)
Antwoord
[1, 3, 4, 1, 5]

De 3 en de 1 op posities 0 en 1 zijn geruild.

Run​

Python
Code-omgeving wordt voorbereid…

Experimenteer​

Probeer voor alle geldige i's achter elkaar, net als in bouwsteen 1:

Python
Code-omgeving wordt voorbereid…
Wat zie je?
start: [3, 1, 4, 1, 5]
i=0: swap → [1, 3, 4, 1, 5]
i=1: laat → [1, 3, 4, 1, 5]
i=2: swap → [1, 3, 1, 4, 5]
i=3: laat → [1, 3, 1, 4, 5]
eind: [1, 3, 1, 4, 5]

Dit is precies één pass van bubble sort over de lijst. De 5 zit nu achteraan op zijn juiste plek. Maar de lijst is nog niet helemaal gesorteerd — er moeten meer passes komen. En [0, 1, 2, 3] uitschrijven werkt alleen voor een lijst van vijf; in de volgende stap wordt dat een range die voor elke lengte klopt.

Wat nu nog mist​

Eén pass is meestal niet genoeg. In de volgende stap zetten we vast wat een pass precies is, en daarna laten we hem herhalen.

Door naar bouwsteen 3: één pass.