Come funzionano la ricerca binaria e il merge sort per il GCSE?

Se stai ripassando gli algoritmi per l'esame di GCSE Computer Science, quattro nomi ricorrono ancora e ancora: ricerca lineare, ricerca binaria, bubble sort e merge sort. Le commissioni d'esame adorano chiederti di tracciare questi algoritmi a mano, identificare il runtime o completare righe di pseudocodice mancanti. Ecco cosa conta davvero per l'esame e oltre.

Ricerca lineare: la base

La ricerca lineare controlla ogni elemento di un elenco, uno alla volta, finché non trova il bersaglio o raggiunge la fine. È tutto.

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

Nel caso peggiore, controlli ogni singolo elemento, quindi è O(n). Nel caso migliore, il bersaglio è il primo, quindi O(1). Gli esaminatori amano chiederti di dichiarare entrambi. La ricerca lineare funziona su dati non ordinati, che è il suo unico vero vantaggio rispetto alla ricerca binaria.

Ricerca binaria: quella che confonde le persone

La ricerca binaria funziona solo su un elenco ordinato. Confronti il bersaglio con l'elemento centrale. Se il bersaglio è più piccolo, scarta la metà superiore; se è più grande, scarta la metà inferiore. Ripeti finché non lo trovi o finché non finisci gli elementi.

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

Questo è O(log n), ed è per questo che è drasticamente più veloce su grandi insiemi di dati. Cerca un elenco ordinato di un milione di elementi e la ricerca lineare potrebbe richiedere fino a un milione di confronti; la ricerca binaria ne richiede circa 20. Gli esaminatori comunemente ti danno un elenco di, diciamo, 16 numeri e ti chiedono di tracciare quali indici vengono controllati — esercitati su carta con penna e matita, non solo nella tua testa.

Bubble sort: semplice ma lento

Il bubble sort percorre ripetutamente l'elenco, scambiando elementi adiacenti se sono nell'ordine sbagliato. Ogni passaggio completo sposta l'elemento non ordinato più grande nella sua posizione corretta alla fine.

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

Il caso peggiore è O(n²) — per ogni elemento, potresti scansionare quasi l'intero elenco di nuovo. È raramente usato nel software reale perché è lento su grandi dati, ma gli esaminatori lo amano perché tracciarlo a mano è gestibile e mostra chiaramente l'idea dei passaggi ripetuti e degli scambi. Sappi come contare il numero di confronti e scambi in una tabella di traccia; è un elemento comune dello schema di valutazione.

Merge sort: dividi e conquista

Il merge sort divide l'elenco a metà ripetutamente finché ogni sottoelenco non ha un elemento, poi unisce questi sottoelenchi in ordine ordinato.

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)

Il passaggio merge confronta gli elementi anteriori di ogni metà e sceglie il più piccolo, ripetendo finché entrambe le metà non sono esaurite. Questo dà O(n log n), che batte il bubble sort comodamente su tutto tranne che su elenchi minuscoli. Le domande GCSE talvolta ti chiedono di disegnare il diagramma di divisione e unione — una forma ad albero che mostra l'elenco che si divide e poi si ricombina. Esercitati a disegnare questo per un elenco di 8 numeri così sei veloce sotto le condizioni d'esame.

Cosa gli esaminatori testano davvero

La maggior parte degli schemi di valutazione vuole che tu sia in grado di:

• Tracciare un algoritmo passo dopo passo e scrivere lo stato dell'elenco dopo ogni passaggio o confronto.
• Indicare la complessità temporale in termini di Big O, o almeno descriverla a parole (