Cum funcționează căutarea binară și merge sort pentru GCSE?

Dacă revizuiești algoritmi pentru GCSE Computer Science, patru denumiri apar din nou și din nou: linear search, binary search, bubble sort și merge sort. Comisiile de examen adoră să te întreb să le urmărești manual, să identifici runtime-ul sau să completezi liniile lipsă din pseudocod. Iată ce contează cu adevărat pentru examen și dincolo.

Linear search: referința de bază

Linear search verifică fiecare element dintr-o listă, unul câte unul, până găsește ținta sau ajunge la final. Atât.

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

În cel mai rău caz, verifici fiecare element, deci este O(n). În cel mai bun caz, ținta este prima, deci O(1). Examinatorii îți place să-ți ceară să spui ambele. Linear search funcționează pe date nesortate, ceea ce este unicul său avantaj real față de binary search.

Binary search: cea care încurcă oamenii

Binary search funcționează doar pe o listă sortată. Compari ținta cu elementul din mijloc. Dacă ținta este mai mică, elimini jumătatea de sus; dacă este mai mare, elimini jumătatea de jos. Repetă până o găsești sau rămâi fără elemente.

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

Aceasta este O(log n), motiv pentru care este dramatic mai rapidă pe seturi mari de date. Caută o listă sortată de un milion de elemente și linear search ar putea avea nevoie de până la un milion de comparații; binary search are nevoie de aproximativ 20. Examinatorii te dau frecvent o listă de, să spunem, 16 numere și te întreb să urmărești care indici sunt verificați — practică aceasta manual cu pix și hârtie, nu doar în cap.

Bubble sort: simplu dar lent

Bubble sort parcurge din nou lista, schimbând elemente adiacente dacă sunt în ordine greșită. Fiecare trecere completă împinge cel mai mare element nesortat pe poziția corectă la final.

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

Cel mai rău caz este O(n²) — pentru fiecare element, ai putea scana din nou aproape toată lista. Este rar folosit în software-ul real pentru că este lent pe date mari, dar examinatorii îl iubesc pentru că urmărirea manuală este realizabilă și arată clar ideea trecerilor și schimburilor repetate. Știi cum să numeri comparațiile și schimburile în tabelul de urmărire; aceasta este un element obișnuit al schemei de notare.

Merge sort: divide și cucerește

Merge sort împarte lista în jumătate în mod repetat până când fiecare sublista are un element, apoi îmbină acele subliste înapoi în ordine sortată.

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)

Pasul merge compară elementele din față ale fiecărei jumătăți și alege pe cea mai mică, repetând până ambele jumătăți sunt folosite. Aceasta dă O(n log n), care bate bubble sort confortabil pe orice altceva decât liste minuscule. Întrebările GCSE uneori te cere să desenezi diagrama de împărțire și îmbinare — o formă de arbore care arată lista împărțită în jos și apoi recombinată. Practică desenarea acestui lucru pentru o listă de 8 numere pentru a fi rapid în condiții de examen.

Ce testează examinatorii cu adevărat

Majorita schemelor de notare vor ca tu să poți:

• Urmări un algoritm pas cu pas și să notezi starea listei după fiecare trecere sau comparație.
• Spune complexitatea timpului în termeni Big O, sau cel puțin descrie-o cu cuvinte (