Cheatsheet — bubble sort

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf

Canonieke implementatie (met early-exit)

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
        if not geswapt:
            break
    return lijst

Basisversie (zonder early-exit)

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

Werkt, maar minder efficiënt op (bijna-)gesorteerde data.

De bouwstenen

1. Buren vergelijken

if lijst[i] > lijst[i + 1]:
    # paar staat fout

Let op: i + 1 moet een geldige index zijn → laatste i is len(lijst) - 2.

2. Twee elementen swappen

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

Pythonische tuple-swap. Geen tijdelijke variabele nodig.

3. Eén pass

for i in range(len(lijst) - 1):       # 0 t/m len-2
    if lijst[i] > lijst[i + 1]:
        lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]

4. Meerdere passes met krimpend bereik

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

Na ronde k staan de laatste k elementen al goed.

5. Early-exit met een vlag

for ronde in range(n - 1):
    geswapt = False                   # binnen de lus!
    for i in range(n - 1 - ronde):
        if lijst[i] > lijst[i + 1]:
            ...
            geswapt = True
    if not geswapt:
        break

Python-syntax

break — uit een lus springen

while True:
    if klaar:
        break        # stop de lus direct

not — logische negatie

if not geswapt:      # gelijk aan: if geswapt == False:
    break

Geneste lussen

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

Buitenste lus zet de ronde. Binnenste loopt door één pass.

Eigenschappen

Hoe snel?

• Beste geval (al gesorteerd + early-exit): O(n) — één pass.
• Slechtste geval (omgekeerd): O(n²) — n − 1 passes.
• Gemiddeld: O(n²).

n	beste (sorted)	slechtste (rev)
100	99	4.950
1.000	999	499.500
10.000	9.999	~50 miljoen

Eigenschappen

• In-place: geen extra lijst nodig.
• Stabiel: gelijke elementen houden hun oorspronkelijke volgorde.
• Adaptief: sneller op (bijna-)gesorteerde data dankzij early-exit.

Veelgemaakte fouten (snel)

Top-3 fouten

1. range(len(lijst)) in binnenste lus zonder - 1 → IndexError.
2. = in if waar je == of > bedoelt → SyntaxError.
3. geswapt = False vóór de buitenste lus → vlag wordt niet gereset → early-exit werkt verkeerd.

---

Klaar met bubble sort? Je hebt nu twee sorteer-algoritmes gezien:

• Selection sort — veel vergelijkingen, weinig swaps, niet stabiel.
• Bubble sort — adaptief, stabiel, simpel.

Volgende stap: sneller sorteren met merge sort of quicksort (O(n log n)) — komt later.