Het complete algoritme

Leerdoel: je ziet alle bouwstenen samen en onderzoekt het algoritme.

Alles samen

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

Zie je de bouwstenen?

• Regel 5 → bouwsteen 1: vergelijk buren (lijst[i] > lijst[i + 1]).
• Regel 6 → bouwsteen 2: swap.
• Regels 4-6 → bouwsteen 3: één pass (range(n - 1 - ronde)).
• Regels 3-7 → bouwsteen 4: meerdere passes.
• Regels 4 + 7 + 8-9 → bouwsteen 5: early-exit met geswapt.

Run

Python

Code-omgeving wordt voorbereid…

Onderzoek — strings en stabiliteit

Python

Code-omgeving wordt voorbereid…

Wat zie je?

• Strings → alfabetisch gesorteerd. Werkt.
• Stabiliteit: (1,b) blijft vóór (1,d); (2,a) blijft vóór (2,c). Bubble sort is stabiel: gelijke elementen behouden hun oorspronkelijke volgorde (omdat we strict > gebruiken — geen swap bij gelijk).

Dat is een verschil met selection sort, die niet stabiel is.

Onderzoek — werk vergelijken

Wat doet bubble sort op verschillende soorten input?

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Ongeveer:

al gesorteerd        passes= 1  vergelijkingen=   49  swaps=0
omgekeerd            passes=49  vergelijkingen= 1225  swaps=1225
willekeurig          passes=~40 vergelijkingen=~1100  swaps=~600
bijna gesorteerd     passes= 2  vergelijkingen=   97  swaps=1

• Al gesorteerd: één pass dankzij early-exit — O(n).
• Omgekeerd: max werk — O(n²).
• Willekeurig: ergens daartussen, dichter bij omgekeerd.
• Bijna gesorteerd (één swap nodig): één pass om de wisseling op te lossen, één pass zonder swap om te bevestigen → klaar. Heel snel — een van de redenen waarom bubble sort soms toch nog gebruikt wordt.

Door naar stap 9: aanpassen →