Controleer Elkeen Afzonderlijk
Lineaire Zoekopdracht: Elk Een Controleren
Stel dat je 10 kaarten hebt met de rug naar beneden, genummerd van 1 tot 10, geschud in willekeurige volgorde.
Je wilt de kaart vinden met het nummer 7.
Je kijkt de kaarten een voor een om, van links naar rechts, totdat je hem vindt.
| Scenario | Omwentelingen nodig |
|----------|------------------|
| Beste geval | 1 omwenteling (gelukkige eerste poging!) |
| Slechtste geval | 10 omwentelingen (het was de laatste kaart) |
| Gemiddeld | ongeveer 5 omwentelingen |
Stel dat je nu 100 kaarten hebt. Gemiddeld: ongeveer 50 omwentelingen.
1000 kaarten? Gemiddeld: ongeveer 500 omwentelingen.
Zie je de patroon? Dubbel de kaarten, dubbel de werklast. De werklast groeit in een rechte lijn.
Informatica-wetenschappers noemen dit lineaire zoekopdracht - lineair betekent dat de werklast groeit zoals een lijn: gestaag en voorspelbaar.
Lineaire zoekopdracht werkt op ELKE lijst, gesorteerd of niet. Dat maakt het eenvoudig. Maar het kan snel worden.
Hoeveel Namen?
Je hebt een lijst van 20 namen van je klas geschreven.
Je moet de naam Zoe vinden.
Je controleert de namen een voor een, van boven naar beneden.
De lijst halveren
Binair Zoeken: Spring naar het Midden
Binair zoeken heeft één regel: de lijst moet eerst gesorteerd worden.
Als je lijst van 20 namen loopt van A naar Z, kun je binair zoeken gebruiken.
Hoe het werkt: open op de middelste naam (naam #10). Vraag: is Zoe voor of na deze naam?
Z komt aan het eind van het alfabet, dus Zoe komt NA de middelste. Gooi de eerste helft weg. Nu heb je alleen nog namen 11-20 over.
Controleer het midden van die 10 namen (naam #15). Z komt na M, dus Zoe komt na naam #15. Gooi namen 11-14 weg. Nu heb je namen 16-20 over.
Houd de lijst halveren. Elk controle verwijdert de helft van de overgebleven namen.
| Lijstgrootte | Maximaal controles met binair zoeken |
|-----------|-------------------------------|
| 20 namen | maximaal 5 controles |
| 1.000 namen | maximaal 10 controles |
| 1.000.000 namen | maximaal 20 controles |
Vergelijk dat met lineaire zoekopdracht op 1.000.000 namen: een gemiddeld van 500.000 controles.
Binair zoeken deelt de lijst elke keer in helften. Helften delen herhaaldelijk bereikt 1 zeer snel - dat is waarom het zo snel blijft.
Vind 'fig' in een Gesorteerde Lijst
Hier is een gesorteerde lijst van 8 woorden:
1. appel 2. banaan 3. kers 4. date 5. ouderebessen 6. fig 7. druif 8. ananas
Je wilt fig vinden met behulp van binair zoeken.
Onthoud: controleer het midden, vraag of je doelwit voor of na komt, en snijd vervolgens de lijst doormidden.
Wisselen van Buren in Volgorde
Bubble Sort: Compare Neighbors & Swap
Bubble sort plaatst een lijst in volgorde door twee aangrenzende items tegelijk te vergelijken.
Als twee buren ongeordend zijn — ruil ze.
Maak steeds passen door de lijst totdat niets meer hoeft te worden omgewisseld.
Voorbeeld: sorteer [5, 3, 8, 1]
Pas 1:
- Vergelijk 5 & 3. 5 > 3, dus ruil → [3, 5, 8, 1]
- Vergelijk 5 & 8. 5 < 8, geen ruil → [3, 5, 8, 1]
- Vergelijk 8 & 1. 8 > 1, dus ruil → [3, 5, 1, 8]
Pas 2:
- Vergelijk 3 & 5. OK → [3, 5, 1, 8]
- Vergelijk 5 & 1. 5 > 1, ruil → [3, 1, 5, 8]
- Vergelijk 5 & 8. OK → [3, 1, 5, 8]
Pas 3:
- Vergelijk 3 & 1. 3 > 1, ruil → [1, 3, 5, 8]
- Vergelijk 3 & 5. OK. Vergelijk 5 & 8. OK.
Klaar! [1, 3, 5, 8] ✓
Opmerking: het grootste getal bubbelt naar het eind van de lijst bij elke pas. Daardoor heet bubble sort zo.
Bubble sort werkt. Het is niet de snelste voor grote lijsten, maar het is gemakkelijk te begrijpen — perfect om te leren.
Sorteer [4, 2, 7, 1] met Bubble Sort
Sorteer deze lijst met bubble sort: [4, 2, 7, 1]
Toon de lijst na elke pas. Tel hoeveel passen het kost om klaar te zijn.