Ga naar hoofdinhoud

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
  1. Regel 3:

    Bouwsteen 4 — meerdere passes: hooguit n - 1 rondes, want elke ronde legt minstens één element definitief goed.

  2. Regel 4:

    Bouwsteen 5, deel één — de vlag gaat elke ronde vers op False; alleen een echte swap zet hem om.

  3. Regel 5:

    Bouwsteen 3 — één pass. De - ronde maakt hem elke ronde korter: de staart is al gesorteerd.

  4. Regel 6:

    Bouwsteen 1 — vergelijk buren. De laatste geldige i is n - 2, want i + 1 moet ook bestaan.

  5. Regel 7-8:

    Bouwsteen 2 — de swap, en de vlag om te onthouden dat er iets veranderde.

  6. Regel 9-10:

    Bouwsteen 5, deel twee — een hele pass zonder swaps betekent: gesorteerd. Eerder stoppen mag dan.

Run​

Python
Code-omgeving wordt voorbereid…

Interactief model

Bubble sort

Vergelijk buren en stop vroeg als er niets wisselt.

Bron referentieStap 0/16Vergelijkingen 0Swaps 0Passes 0Resultaat -
03
11
24
31
45

Start

We vergelijken steeds twee buren en swappen als ze verkeerd staan.

Onderzoek — strings en stabiliteit​

Python
Code-omgeving wordt voorbereid…
Wat zie je?
  • Strings komen alfabetisch te staan.
  • Stabiliteit: [(5, 'Noor'), (5, 'Bo'), (7, 'Sam'), (7, 'Ali')]. Sam stond vóór Ali en staat er nog steeds vóór. Bubble sort is stabiel: twee gelijke buren wisselen nooit, want de vergelijking is strikt >. Vergelijk je de hele tuple in plaats van alleen het cijfer, dan sorteert Python ook op naam en zie je hier niets.

Dat is een verschil met selection sort, die met dezelfde lijst Sam achter Ali zet.

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, dus O(n).
  • Omgekeerd: het maximale werk, O(n²).
  • Willekeurig: daartussenin, en dichter bij omgekeerd dan je zou denken.
  • Bijna gesorteerd, met één wisseling nodig: één pass om die wisseling op te lossen en één om te bevestigen dat het klaar is. Zo snel dat bubble sort daar soms nog echt voor gebruikt wordt.

Door naar aanpassen.