Ga naar hoofdinhoud

Bouwsteen 3 — één pass door de lijst

Leerdoel: je weet precies tot welke index de binnenste lus loopt, en waarom er - 1 bij hoort.

Wat we willen​

Eén pass = één keer door de lijst lopen, elk paar buren bekijken en zo nodig swappen.

De - 1 is cruciaal​

Bij elke vergelijking pakken we lijst[i] en lijst[i + 1]. De laatste geldige i is dus len(lijst) - 2 (zodat i + 1 precies de laatste index is).

for i in range(len(lijst) - 1):     # 0, 1, ..., len-2
    ...

Vergeten we de - 1?

for i in range(len(lijst)):         # 0, 1, ..., len-1
    if lijst[i] > lijst[i + 1]:     # crash bij i = len-1
        ...

→ IndexError: list index out of range op de laatste iteratie. Klassieke beginnersfout.

Voorspel​

Wat denk je dat dit print?

def een_pass(lijst):
    for i in range(len(lijst) - 1):
        if lijst[i] > lijst[i + 1]:
            lijst[i], lijst[i + 1] = lijst[i + 1], lijst[i]
    return lijst

print(een_pass([3, 1, 4, 1, 5]))
print(een_pass([5, 4, 3, 2, 1]))
print(een_pass([1, 2, 3, 4, 5]))
Antwoord
[1, 3, 1, 4, 5]
[4, 3, 2, 1, 5]
[1, 2, 3, 4, 5]
  • [3, 1, 4, 1, 5] → de 5 borrelt naar achteren (was al achteraan); de binnenste-paar-swaps gebeuren.
  • [5, 4, 3, 2, 1] (omgekeerd) → de 5 borrelt netjes helemaal naar achteren in één pass. De rest is nog wel rommelig.
  • [1, 2, 3, 4, 5] (al gesorteerd) → niets verandert.

Run​

Python
Code-omgeving wordt voorbereid…

Visualiseer — het grootste borrelt naar achteren​

Python
Code-omgeving wordt voorbereid…
Wat zie je?
start: [4, 2, 7, 1, 3]
  i=0: swap → [2, 4, 7, 1, 3]
  i=2: swap → [2, 4, 1, 7, 3]
  i=3: swap → [2, 4, 1, 3, 7]
eind:  [2, 4, 1, 3, 7]

Drie swaps. De 7 (grootste) is helemaal naar achteren gegaan. Maar de 1 moet nog twee plekken naar voren — daarvoor zijn meer passes nodig.

Wat nu nog mist​

We hebben één pass. We willen het herhalen tot de lijst gesorteerd is.

Door naar bouwsteen 4: meerdere passes →