Bouw zelf — vergelijk early-exit aan en uit

Leerdoel: je meet zelf hoeveel de early-exit-optimalisatie scheelt op al-gesorteerde input, en visualiseert het verschil.

Opdracht

Schrijf twee versies van bubble sort:

1. bubble_sort_zonder_exit — zonder early-exit. Doet altijd n − 1 passes.
2. bubble_sort_met_exit — met early-exit (zoals het complete algoritme).

Vergelijk ze op meerdere lijst-typen en plot het verschil in vergelijkingen.

Python

Code-omgeving wordt voorbereid…

Tip

Beide versies hebben dezelfde basis-structuur. Het verschil zit in:

• Bij bubble_sort_zonder_exit: geen geswapt-vlag, geen break.
• Bij bubble_sort_met_exit: alles wat je in bouwsteen 5 hebt geleerd.

Beide moeten het aantal vergelijkingen terug geven, niet de lijst.

Antwoord

De code zoals hierboven al gegeven werkt — de aangegeven uitwerking is dezelfde. Het echte werk zit in de interpretatie van het resultaat.

Wat zie je in de grafiek?

Interpretatie

• Al gesorteerd: zonder exit doet hij alle passes (~n²/2 vergelijkingen). Met exit slechts één pass (n − 1 vergelijkingen). Enorme besparing.
• Bijna sorted: één element fout staat → met early-exit nog steeds maar paar passes. Zonder exit weer alle passes.
• Omgekeerd: geen verschil. Geen enkele pass is zonder swaps → exit helpt niet.
• Willekeurig: matige besparing — typisch eindigt early-exit een paar rondes voor het einde.

Conclusie: early-exit is gratis veel sneller op bijna-gesorteerde data. Op willekeurige of omgekeerde data is hij ongeveer gratis (geen verlies), dus altijd inschakelen.

Uitdaging (optioneel)

Implementeer cocktail sort: een bubble sort die afwisselend van links naar rechts en van rechts naar links door de lijst loopt. In één rondtrip bubbelt de grootste naar rechts en de kleinste naar links — minder overall passes voor sommige inputs.

Door naar stap 11: veelgemaakte fouten →