Wie funktionieren binäre Suche und Merge Sort für GCSE?

Wenn du Algorithmen für GCSE Computer Science wiederholst, tauchen vier Namen immer wieder auf: lineare Suche, binäre Suche, Bubble Sort und Merge Sort. Prüfungskommissionen lieben es, dich zu bitten, diese von Hand nachzuvollziehen, die Laufzeit zu nennen oder fehlende Pseudocode-Zeilen auszufüllen. Hier ist, was wirklich für die Prüfung und darüber hinaus zählt.

Lineare Suche: die Basis

Lineare Suche prüft jedes Element in einer Liste, eins nach dem anderen, bis sie das Ziel findet oder das Ende erreicht. Das war's.

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

Im schlimmsten Fall prüfst du jedes Element, also ist es O(n). Im besten Fall ist das Ziel das erste, also O(1). Prüfer fragen gerne danach, dass du beides nennst. Lineare Suche funktioniert mit unsortierten Daten, was ihr einziger echter Vorteil gegenüber binärer Suche ist.

Binäre Suche: die, die Leute verwirrt

Binäre Suche funktioniert nur mit einer sortierten Liste. Du vergleichst das Ziel mit dem mittleren Element. Wenn das Ziel kleiner ist, verwirfst du die obere Hälfte; wenn größer, verwirfst du die untere Hälfte. Wiederhole bis du es findest oder keine Elemente mehr hast.

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

Das ist O(log n), deshalb ist es dramatisch schneller bei großen Datenmengen. Suche in einer sortierten Liste mit einer Million Elementen und lineare Suche könnte bis zu eine Million Vergleiche brauchen; binäre Suche braucht etwa 20. Prüfer geben dir häufig eine Liste von zum Beispiel 16 Zahlen und fragen dich, welche Indizes geprüft werden — übe das von Hand mit Stift und Papier, nicht nur im Kopf.

Bubble Sort: einfach aber langsam

Bubble Sort durchläuft die Liste wiederholt und tauscht benachbarte Elemente aus, wenn sie in der falschen Reihenfolge sind. Jeder vollständige Durchgang schiebt das größte unsortierte Element an seine richtige Position am Ende.

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])

Der schlimmste Fall ist O(n²) — für jedes Element scannst du möglicherweise fast die ganze Liste wieder. Es wird in echter Software selten verwendet, weil es bei großen Daten langsam ist, aber Prüfer mögen es, weil das Nachvollziehen von Hand handhabbar ist und die Idee wiederholter Durchläufe und Tausche klar zeigt. Wisse, wie du die Anzahl der Vergleiche und Tausche in einer Nachverfolgungstabelle zählst; das ist ein häufiger Punkt im Bewertungsschema.

Merge Sort: Teile und Herrsche

Merge Sort teilt die Liste wiederholt in zwei Hälften, bis jede Teilliste ein Element hat, dann fügt diese Teillisten wieder in sortierter Reihenfolge zusammen.

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)

Der Merge-Schritt vergleicht die vordersten Elemente jeder Hälfte und wählt das kleinere, und wiederholt dies, bis beide Hälften verwendet sind. Das ergibt O(n log n), was Bubble Sort bei allem außer winzigen Listen deutlich schlägt. GCSE-Fragen fragen dich manchmal, das Aufteils- und Merge-Diagramm zu zeichnen — eine Baumform, die zeigt, wie die Liste nach unten aufgeteilt und dann wieder zusammengesetzt wird. Übe, das für eine Liste von 8 Zahlen zu zeichnen, damit du es unter Prüfungsbedingungen schnell kannst.

Was Prüfer wirklich testen

Die meisten Bewertungsschemata wollen, dass du folgendes kannst:

• Einen Algorithmus Schritt für Schritt nachvollziehen und den Zustand der Liste nach jedem Durchgang oder Vergleich aufschreiben.
• Zeitkomplexität in Big O Begriffen nennen, oder sie zumindest in Worten beschreiben (