Lijst
Het idee: waarden staan in een volgorde en je kunt ze per positie bekijken.
getallen[1] → 3
Algoritmen · Hoofdstuk 1 · Sorteren
Sorteren: van lijst naar algoritme
Hoe zet een computer [7, 3, 8, 2] op volgorde? Je leert eerst hoe zo’n lijst wordt bewaard. Daarna zie je drie sorteerstrategieën bewegen en vergelijk je hoe snel ze groeien.
01Eerst: wat wordt er gesorteerd?
Een lijst is een geordende verzameling waarden. “Geordend” betekent hier: ieder element heeft een vaste positie, niet dat de waarden al van klein naar groot staan.
index
0123
waarde
7382
getallen = [7, 3, 8, 2]
🔮 Voorspel de uitvoer
Indexen beginnen bij 0 — net als range() in les 4. Wat print dit programma?
getallen = [7, 3, 8, 2]
print(getallen[1] + getallen[3])
5
getallen[1] is het tweede element (3) en getallen[3] het vierde (2), want tellen begint bij 0. Dus 3 + 2 = 5. En getallen[4]? Dat bestaat niet — dan krijg je een IndexError.
Array
Een rij aaneengesloten geheugenvakken. Bij een vaste array ligt de capaciteit vooraf vast.
capaciteit = 4
Dynamische array
Gedraagt zich als een array, maar kan groeien door zo nodig een groter blok te maken.
getallen.append(5)
lengte = 3
1249vrijvrij
capaciteit = 5
lengte = 4
12497vrij
capaciteit = 5
Python-koppeling. De ingebouwde list wordt in de gebruikelijke Python-implementatie CPython opgeslagen als een dynamische array. Daardoor is getallen[i] snel en is achteraan toevoegen meestal snel. Vooraan invoegen is duurder: alle volgende elementen moeten opschuiven.
Waarde op index lezenO(1)
Achteraan toevoegengemiddeld O(1)
Vooraan invoegenO(n)
02Drie manieren om te sorteren
Een sorteeralgoritme is een precies stappenplan dat dezelfde invoer steeds in de gewenste volgorde zet. De drie algoritmen hieronder bereiken hetzelfde doel, maar pakken het totaal anders aan.
Agemiddeld O(n²)
Bubble Sort — buren vergelijken
Loop steeds van links naar rechts. Staan twee buren verkeerd? Wissel ze om. Na iedere ronde staat het grootste overgebleven getal helemaal rechts.
start
5241
5 > 2 → wisseldaarna
2541
5 > 4 → wisselronde klaar
2415
5 staat vast✓ makkelijk te begrijpen✓ weinig extra geheugen− veel vergelijkingen
🔮 Voorspel de lijst
Bubble Sort begint aan de lijst [4, 1, 3, 2]. Hoe ziet de lijst eruit na één volledige ronde (één keer van links naar rechts)?
[1, 3, 2, 4]
Stap voor stap: 4 > 1 → wissel → [1, 4, 3, 2]; 4 > 3 → wissel → [1, 3, 4, 2]; 4 > 2 → wissel → [1, 3, 2, 4]. Nog niet alles staat goed, maar één ding weet je zeker: het grootste getal staat na één ronde helemaal rechts.
Bekijk de Python-code
def bubble_sort(getallen):
n = len(getallen)
for einde in range(n - 1, 0, -1):
gewisseld = False
for i in range(einde):
if getallen[i] > getallen[i + 1]:
tijdelijk = getallen[i]
getallen[i] = getallen[i + 1]
getallen[i + 1] = tijdelijk
gewisseld = True
if gewisseld == False:
return getallen
return getallen
Baltijd O(n log n)
Merge Sort — splitsen en samenvoegen
Splits de lijst steeds doormidden tot elk deel één element heeft. Voeg daarna twee gesorteerde delen steeds netjes samen.
8362
splits ↓
83
62
splits ↓ splits ↓
8
3
6
2
voeg gesorteerd samen ↓
2368
✓ voorspelbaar snel✓ behoudt gelijke volgorde− extra geheugen nodig
Bekijk de Python-code
def voeg_samen(links, rechts):
resultaat = []
i = 0
j = 0
while i < len(links) and j < len(rechts):
if links[i] <= rechts[j]:
resultaat.append(links[i])
i = i + 1
else:
resultaat.append(rechts[j])
j = j + 1
resultaat = resultaat + links[i:]
resultaat = resultaat + rechts[j:]
return resultaat
def merge_sort(getallen):
if len(getallen) <= 1:
return getallen
midden = len(getallen) // 2
links = merge_sort(getallen[:midden])
rechts = merge_sort(getallen[midden:])
return voeg_samen(links, rechts)
De hulpfunctie voeg_samen() kiest steeds de kleinste voorste waarde van de twee gesorteerde delen.
Cgemiddeld O(n log n)
Quick Sort — verdelen rond een pivot
Kies één waarde als pivot. Zet kleinere waarden links, grotere rechts en herhaal dat binnen beide groepen.
83625
pivot = 5kleiner
32
pivot
5
groter
86
✓ in de praktijk vaak snel✓ weinig extra opslag mogelijk− slechte pivot kan O(n²) geven
Bekijk de Python-code
def quick_sort(getallen):
if len(getallen) <= 1:
return getallen
pivot = getallen[-1]
lager = []
gelijk = []
hoger = []
for getal in getallen:
if getal < pivot:
lager.append(getal)
elif getal == pivot:
gelijk.append(getal)
else:
hoger.append(getal)
return quick_sort(lager) + gelijk + quick_sort(hoger)
03Interactief sorteerlab
Kies een algoritme en loop stap voor stap door dezelfde lijst. Oranje balken worden nu bekeken, paars is de pivot en groen staat al op de juiste plek.
Stap 1 / 1
De ongesorteerde lijst staat klaar.
04Looptijd: hoe groeit het werk?
Big O beschrijft niet het exacte aantal milliseconden. Het vertelt hoe snel de hoeveelheid werk groeit wanneer de invoer n groter wordt.
naantal waarden
O(n²)ongeveer n × n werk
O(n log n)splitsen + alle waarden bekijken
🔮 Voorspel de groei
Een lijst wordt 10 keer zo lang (van 100 naar 1.000 waarden). Ongeveer hoeveel keer zoveel werk krijgt een O(n²)-algoritme zoals Bubble Sort?
± 100 keer zoveel werk
Bij O(n²) telt de lengte kwadratisch mee: 10 keer zo lang betekent 10 × 10 = 100 keer zoveel stappen (van 10.000 naar 1.000.000). Een O(n log n)-algoritme groeit veel rustiger: van ± 664 naar ± 9.966 stappen — nog geen 15 keer zoveel.
| Algoritme | Beste geval | Gemiddeld | Slechtste geval | Extra geheugen | Stabiel? |
|---|---|---|---|---|---|
| Bubble Sort* | O(n) | O(n²) | O(n²) | O(1) | Ja |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | gem. O(log n) | Nee |
* Bubble Sort haalt O(n) alleen met de controle gewisseld == False wanneer de lijst al gesorteerd is. De geheugenwaarde bij Quick Sort hoort bij een efficiënte in-place variant; de eenvoudigere voorbeeldcode hierboven maakt tijdelijke lijsten en gebruikt daardoor meer geheugen.
Welke kies je?
Bubble Sort om het principe van vergelijken en wisselen te leren — zelden voor grote echte datasets.
Merge Sort als je gegarandeerd O(n log n) en een stabiele sortering wilt.
Quick Sort als gemiddelde snelheid belangrijk is en je een goede pivotstrategie gebruikt.
In gewone Python-code: gebruik meestal sorted(lijst) of lijst.sort(). Python gebruikt Timsort, een slim hybride algoritme met O(n log n) als slechtste looptijd.
🧠 Test jezelf
Vijf korte vragen over lijsten, de drie algoritmen en looptijd. Je ziet meteen of je antwoord klopt, met uitleg.