Bouwsteen 5 — vroeg klaar als er niets meer hoeft

Leerdoel: je voegt een vlag toe die detecteert wanneer een pass geen swaps had — dat betekent dat de lijst al klaar is.

Het idee

Komt een hele pass voorbij zonder één enkele swap, dan stonden alle paren al goed en is de lijst gesorteerd. Verder gaan heeft dan geen zin.

Daarvoor houd je een vlag bij, geswapt:

• Aan het begin van elke pass zet je hem op False.
• Bij elke swap zet je hem op True.
• Staat hij aan het eind van de pass nog op False, dan spring je met break uit de buitenste lus.

Voorspel

Wat denk je dat dit print?

def bubble_sort(lijst):
    n = len(lijst)
    for ronde in range(n - 1):
        geswapt = False
        for i in range(n - 1 - ronde):
            if lijst[i] > lijst[i + 1]:
                lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
                geswapt = True
        print(f"ronde {ronde}: lijst={lijst}, geswapt={geswapt}")
        if not geswapt:
            break
    return lijst

bubble_sort([1, 2, 3, 4, 5])

Antwoord

ronde 0: lijst=[1, 2, 3, 4, 5], geswapt=False

Eén ronde zonder swaps, dus break. Op een gesorteerde lijst is bubble sort klaar na één pass van n − 1 vergelijkingen, en dat is O(n).

Run

Python

Code-omgeving wordt voorbereid…

Wat zie je?

• Al gesorteerd: één ronde, geswapt blijft False, en de break volgt meteen.
• Omgekeerd: vier rondes, 0 tot en met 3, met in elke ronde swaps. Pas na ronde 3 staat alles goed, en dat is ook de laatste ronde die range(n - 1) toestaat.
• Bijna gesorteerd: twee rondes. In ronde 0 wisselen de 4 en de 3, en de ronde daarna bevestigt zonder swaps dat het klaar is.

Waarom is dit zo handig?

Vooral bij data die al bijna op volgorde staat, en dat komt vaker voor dan je denkt: een gesorteerde lijst waar één element bij is gekomen, bijvoorbeeld. Met early-exit is bubble sort daar O(n) in plaats van O(n²).

Wat nu?

Je hebt alle bouwstenen. Tijd om ze samen te zien werken.

Door naar het complete algoritme.