Bouw zelf — vergelijk early-exit aan en uit

Leerdoel: je meet zelf hoeveel de early-exit-optimalisatie scheelt op verschillende soorten input.

Opdracht

Schrijf twee versies van bubble sort die niet de lijst teruggeven, maar het aantal vergelijkingen dat ze deden:

1. bubble_sort_zonder_exit(lijst) — altijd n − 1 passes, geen vlag, geen break.
2. bubble_sort_met_exit(lijst) — met de geswapt-vlag uit bouwsteen 5.

Verwacht op [1, 2, 3, 4, 5]: zonder exit 10 vergelijkingen, met exit 4. Op [5, 4, 3, 2, 1]: allebei 10.

De startcode roept beide functies aan op vier soorten lijsten van 100 getallen en print de aantallen. Alleen de twee functies hoef je te schrijven.

Python

Code-omgeving wordt voorbereid…

Tip

Neem bubble_sort_basis uit bouwsteen 4 als basis voor de versie zonder exit, en bubble_sort uit bouwsteen 5 voor de versie mét. Zet in allebei vergelijkingen += 1 als eerste regel in de binnenste lus, vóór de if. Geef aan het eind vergelijkingen terug in plaats van de lijst.

Antwoord

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

def bubble_sort_met_exit(lijst):
    n = len(lijst)
    vergelijkingen = 0
    for ronde in range(n - 1):
        geswapt = False
        for i in range(n - 1 - ronde):
            vergelijkingen += 1
            if lijst[i] > lijst[i + 1]:
                lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
                geswapt = True
        if not geswapt:
            break
    return vergelijkingen

Wat zie je?

Interpretatie

Voor 100 getallen:

Lijst	Zonder exit	Met exit
al gesorteerd	4950	99
bijna gesorteerd	4950	197
omgekeerd	4950	4950
willekeurig	4950	meestal 4500 tot 4950

• Al gesorteerd: zonder exit doet hij alle 99 passes, met exit één. Vijftig keer minder werk.
• Bijna gesorteerd: één pass om de wisseling te herstellen, één pass om te bevestigen dat er niets meer hoeft.
• Omgekeerd: geen verschil. Elke pass wisselt iets, dus de vlag staat nooit op False.
• Willekeurig: een klein verschil. De laatste paar passes hebben soms niets meer te doen, meer niet.

Early-exit kost dus niets op lastige input en scheelt enorm op input die al bijna goed staat. Daarom zet je hem altijd aan.

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 heen-en- weer bubbelt de grootste naar rechts én de kleinste naar links. Test op [2, 3, 4, 5, 1]: bubble sort heeft daar vier passes voor nodig, cocktail sort één heen-en-weer.

Tip

Houd twee grenzen bij: begin en eind. Na een pass naar rechts staat het grootste getal op eind, dus eind gaat één omlaag. Na een pass naar links staat het kleinste op begin, dus begin gaat één omhoog. Voor de pass naar links loop je met range(eind - 1, begin - 1, -1) achteruit.

Antwoord

def cocktail_sort(lijst):
    begin = 0
    eind = len(lijst) - 1
    geswapt = True
    while geswapt:
        geswapt = False
        for i in range(begin, eind):
            if lijst[i] > lijst[i + 1]:
                lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
                geswapt = True
        eind -= 1
        if not geswapt:
            break
        geswapt = False
        for i in range(eind - 1, begin - 1, -1):
            if lijst[i] > lijst[i + 1]:
                lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
                geswapt = True
        begin += 1
    return lijst

print(cocktail_sort([2, 3, 4, 5, 1]))             # [1, 2, 3, 4, 5]
print(cocktail_sort([3, 1, 4, 1, 5, 9, 2, 6]))    # [1, 1, 2, 3, 4, 5, 6, 9]

De 1 staat helemaal achteraan en moet naar voren. Bubble sort schuift hem elke pass één plek op; de pass naar links van cocktail sort brengt hem in één keer naar voren.

Door naar veelgemaakte fouten.