Één voor één controleren
Lineair zoeken: controleer alles één voor één
Stel je voor dat je 10 kaarten hebt liggen, genummerd 1 tot en met 10, in willekeurige volgorde geschud.
Je wilt de kaart met het getal 7 vinden.
Je draait kaarten één voor één om, van links naar rechts, totdat je het vindt.
| Scenario | Aantal controlles nodig |
|---|---|
| Beste geval | 1 controle (gelukkig eerste poging!) |
| Slechtste geval | 10 controlles (het was de laatste kaart) |
| Gemiddeld | ongeveer 5 controlles |
Stel je nu 100 kaarten voor. Gemiddeld: ongeveer 50 controlles.
1.000 kaarten? Gemiddeld: ongeveer 500 controlles.
Zie je het patroon? Twee keer zoveel kaarten, twee keer zoveel werk. Het werk groeit in een rechte lijn.
Informatici noemen dit lineair zoeken — lineair betekent dat het werk groeit als een lijn: constant & voorspelbaar.
Lineair zoeken werkt op ELKE lijst, gesorteerd of niet. Dat maakt het eenvoudig. Maar het kan traag worden.
Hoeveel namen?
Je hebt een klassenlijst van 20 namen opgeschreven in willekeurige volgorde.
Je moet de naam Zoe vinden.
Je controleert namen één voor één, van boven naar beneden op de lijst.
Verdeel de lijst in tweeën
Binair zoeken: springt naar het midden
Binair zoeken heeft één regel: de lijst moet eerst gesorteerd zijn.
Als je lijst van 20 namen van A tot Z gaat, kun je binair zoeken gebruiken.
Hoe het werkt: open op de middelste naam (naam #10). Vraag je af: komt Zoe voor of na deze naam?
Z komt dicht bij het einde van het alfabet, dus Zoe komt NA het midden. Gooi de eerste helft weg. Nu heb je slechts de namen 11-20 over.
Controleer het midden van die 10 namen (naam #15). Z komt na M, dus Zoe komt na naam #15. Gooi de namen 11-14 weg. Nu heb je de namen 16-20.
Blijf halveren. Elke controle verwijdert de helft van de resterende namen.
| Aantal namen | Max controlles met binair zoeken |
|---|---|
| 20 namen | maximaal 5 controlles |
| 1.000 namen | maximaal 10 controlles |
| 1.000.000 namen | maximaal 20 controlles |
Vergelijk dat met lineair zoeken op 1.000.000 namen: gemiddeld 500.000 controlles.
Binair zoeken halveert de lijst telkens. Telkens halveren bereikt 1 heel snel — daarom blijft het zo snel.
Vind 'framboos' in een gesorteerde lijst
Hier is een gesorteerde lijst van 8 woorden:
1. appel 2. banaan 3. citroen 4. dadelpalm 5. eikel 6. framboos 7. granaatappel 8. hazelnoot
Je wilt framboos vinden met behulp van binair zoeken.
Onthoud: controleer het midden, vraag je af of je doel ervoor of erna komt, halveer vervolgens de lijst.
Buurtjes ruilen voor volgorde
Bubble sort: Vergelijk buren & wissel
Bubble sort zet een lijst in volgorde door twee buuritems tegelijkertijd te vergelijken.
Als twee buren niet in orde zijn — wissel ze.
Blijf passes doen door de lijst totdat niets meer moet worden verwisseld.
Voorbeeld: sorteer [5, 3, 8, 1]
Pass 1:
- Vergelijk 5 & 3. 5 > 3, dus wissel → [3, 5, 8, 1]
- Vergelijk 5 & 8. 5 < 8, geen wissel → [3, 5, 8, 1]
- Vergelijk 8 & 1. 8 > 1, dus wissel → [3, 5, 1, 8]
Pass 2:
- Vergelijk 3 & 5. OK → [3, 5, 1, 8]
- Vergelijk 5 & 1. 5 > 1, wissel → [3, 1, 5, 8]
- Vergelijk 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Vergelijk 3 & 1. 3 > 1, wissel → [1, 3, 5, 8]
- Vergelijk 3 & 5. OK. Vergelijk 5 & 8. OK.
Klaar! [1, 3, 5, 8] ✓
Let op: het grootste getal borrelt naar het einde van de lijst in elke pass. Zo krijgt bubble sort zijn naam.
Bubble sort werkt. Het is niet het snelste voor grote lijsten, maar het is gemakkelijk te begrijpen — perfect voor leren.
Sorteer [4, 2, 7, 1] met Bubble Sort
Sorteer deze lijst met behulp van bubble sort: [4, 2, 7, 1]
Toon de lijst na elke pass. Tel hoeveel passes nodig zijn om klaar te zijn.