Hoe werken binair zoeken en merge sort voor GCSE?

Als je algoritmen herhaalt voor GCSE Computer Science, komen vier namen steeds terug: lineair zoeken, binair zoeken, bubble sort en merge sort. Examenorganisaties stellen graag vragen over het uitwerken van deze algoritmen met de hand, het bepalen van de runtime, of het invullen van ontbrekende pseudocode-regels. Hier staat wat echt belangrijk is voor het examen en daarna.

Lineair zoeken: de basis

Lineair zoeken controleert elk item in een lijst, één voor één, totdat het doel wordt gevonden of het einde wordt bereikt. Dat is alles.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

In het ergste geval controleer je elk element, dus het is O(n). In het beste geval staat het doel eerst, dus O(1). Examinatoren vragen graag dat je beide opgeeft. Lineair zoeken werkt op ongesorteerde gegevens, wat het voornaamste voordeel ervan ten opzichte van binair zoeken is.

Binair zoeken: datgene waar mensen mee worstelen

Binair zoeken werkt alleen op een gesorteerde lijst. Je vergelijkt het doel met het middelste item. Als het doel kleiner is, verwerp je de bovenste helft; als het groter is, verwerp je de onderste helft. Herhaal tot je het gevonden hebt of geen items meer over zijn.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

Dit is O(log n), wat het dramatisch sneller maakt bij grote datasets. Een gesorteerde lijst van een miljoen items doorzoeken en lineair zoeken kan tot een miljoen vergelijkingen nodig hebben; binair zoeken heeft er ongeveer 20 nodig. Examinatoren geven je vaak bijvoorbeeld een lijst van 16 getallen en vragen je uit te werken welke indices worden gecontroleerd — oefen dit met pen en papier, niet alleen in je hoofd.

Bubble sort: simpel maar langzaam

Bubble sort loopt herhaaldelijk door de lijst en wisselt aangrenzende items uit als ze in de verkeerde volgorde staan. Elke volledige doorgang plaatst het grootste ongesorteerde item op zijn juiste plaats aan het einde.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

Het ergste geval is O(n²) — voor elk element kun je bijna de hele lijst opnieuw scannen. Het wordt zelden in echte software gebruikt omdat het langzaam is bij grote gegevens, maar examinatoren houden ervan omdat het uitwerken met de hand hanteerbaar is en het duidelijk het idee van herhaalde doorgang en wissels laat zien. Weet hoe je het aantal vergelijkingen en wissels in een traceertabel telt; dat is een veelvoorkomend onderdeel van het beoordelingsschema.

Merge sort: verdeel en heers

Merge sort splitst de lijst herhaaldelijk in tweeën totdat elk sublijstje één item heeft, en voegt die sublijstjes dan weer in gesorteerde volgorde samen.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

De merge-stap vergelijkt de eerste items van elke helft en kiest de kleinere, herhaaldelijk totdat beide helften op zijn. Dit geeft O(n log n), wat bubble sort gemakkelijk verslaat behalve bij hele kleine lijsten. GCSE-vragen vragen je soms het split-en-merge-diagram te tekenen — een boomvorm die laat zien hoe de lijst omlaag splitst en zich dan weer samenstelt. Oefen dit tekenen voor een lijst van 8 getallen zodat je het snel onder examenomstandigheden doet.

Wat examinatoren eigenlijk toetsen

De meeste beoordelingsschema's willen dat je kunt:

• Een algoritme stap voor stap uitwerken en de staat van de lijst na elke doorgang of vergelijking opschrijven.
• Tijdcomplexiteit in Big O-termen aangeven, of het op zijn minst in woorden beschrijven (