Controleer Een voor Een
Lineaire Zoektocht: Controleer Elk Een
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 kant de kaarten een voor een om, van links naar rechts, tot je hem vindt.
| Scenario | Omdraaien nodig |
|----------|----------------|
| Beste geval | 1 omdraai (gelukkige eerste poging!) |
| Slechtste geval | 10 omdraaien (het was de laatste kaart) |
| Gemiddeld | ongeveer 5 omdraaien |
Stel dat je nu 100 kaarten hebt. Gemiddeld: ongeveer 50 omdraaien.
1000 kaarten? Gemiddeld: ongeveer 500 omdraaien.
Zie je de patroon? Dubbel de kaarten, dubbel de werklast. De werklast groeit in een rechte lijn.
Computerscientisten noemen dit lineaire zoektocht - lineair betekent dat de werklast groeit zoals een lijn: gestaag en voorspelbaar.
Lineaire zoektocht werkt op ELKE lijst, gesorteerd of niet. Dat maakt het eenvoudig. Maar het kan langzamer worden.
Hoeveel Namens?
Je hebt een klaslijst van 20 namen geschreven in willekeurige volgorde.
Je moet de naam Zoe vinden.
Je controleert namen een voor een, van boven naar beneden.
De lijst halveren
Binair Zoeken: Naar het Midden Springen
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 het halveren aan. 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 lineair zoeken op 1.000.000 namen: een gemiddeld van 500.000 controles.
Binair zoeken halveert de lijst elke keer. Halveren herhalen snel 1 bereiken - 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.
Herinner: controleer het midden, vraag of je doelwit voor of na komt, en snijd de lijst vervolgens doormidden.
Wisselen van Aanbidders in Volgorde
Bubbel Sorteren: Vergelijk Aanbidders & Wisselen
Bubble sort plaatst een lijst in volgorde door twee aangrenzende items tegelijk te vergelijken.
Als twee buurten ongeordend zijn — verwissel ze.
Maak steeds passes door de lijst totdat niets hoeft te verwisselen.
Forbeeld: sorteer [5, 3, 8, 1]
Pass 1:
- Vergelijk 5 & 3. 5 > 3, dus verwissel → [3, 5, 8, 1]
- Vergelijk 5 & 8. 5 < 8, geen verwisseling → [3, 5, 8, 1]
- Vergelijk 8 & 1. 8 > 1, dus verwissel → [3, 5, 1, 8]
Pass 2:
- Vergelijk 3 & 5. OK → [3, 5, 1, 8]
- Vergelijk 5 & 1. 5 > 1, verwissel → [3, 1, 5, 8]
- Vergelijk 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Vergelijk 3 & 1. 3 > 1, verwissel → [1, 3, 5, 8]
- Vergelijk 3 & 5. OK. Vergelijk 5 & 8. OK.
Gedaan! [1, 3, 5, 8] ✓
Opmerking: de grootste getal bubbelt naar het einde van de lijst bij elke pas. Daarom heet bubble sort zo.
Bubble sort werkt. Het is niet de snelste voor grote lijsten, maar het is eenvoudig om 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 passes het kost om klaar te zijn.