Bouwsteen 4 — herhalen tot het klopt

Leerdoel: je verpakt de "één pass"-logica in een buitenste lus die genoeg keer herhaalt om de hele lijst te sorteren.

Hoe vaak moet je herhalen?

Per pass komt het grootste-van-de-rest naar achteren. Voor n elementen zijn n − 1 passes altijd genoeg: staat de rest goed, dan staat het laatste element vanzelf ook goed.

for ronde in range(len(lijst) - 1):
    for i in range(len(lijst) - 1):
        if lijst[i] > lijst[i + 1]:
            lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]

Voorspel

Wat denk je dat dit print?

def bubble_sort_basis(lijst):
    n = len(lijst)
    for ronde in range(n - 1):
        for i in range(n - 1):
            if lijst[i] > lijst[i + 1]:
                lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
    return lijst

print(bubble_sort_basis([3, 1, 4, 1, 5]))
print(bubble_sort_basis([5, 4, 3, 2, 1]))
print(bubble_sort_basis([1, 2, 3, 4, 5]))

Antwoord

[1, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

Alle drie gesorteerd.

Run

Python

Code-omgeving wordt voorbereid…

Een kleine optimalisatie

Na ronde k staan de laatste k elementen al goed. We hoeven dus niet elke ronde tot het einde te kijken — we kunnen één positie eerder stoppen per ronde:

for ronde in range(n - 1):
    for i in range(n - 1 - ronde):     # steeds 1 minder
        ...

Dat scheelt werk zonder dat de logica verandert: de staart die al goed staat laat je met rust.

Python

Code-omgeving wordt voorbereid…

Wat nu nog mist

Op een lijst die al gesorteerd is doet dit nog steeds n − 1 passes, en dat is verspild werk: zodra een ronde geen enkele swap doet, is de lijst klaar. Die vroege uitstap bouw je in de volgende stap.

Door naar bouwsteen 5: early-exit.