Comment fonctionnent la recherche binaire et le tri fusion pour le GCSE ?

Si vous révisez les algorithmes pour l'examen GCSE Computer Science, quatre noms reviennent sans cesse : recherche linéaire, recherche binaire, tri à bulles et tri fusion. Les organismes d'examen adorent vous demander de les tracer à la main, de repérer la complexité d'exécution ou de compléter des lignes de pseudocode manquantes. Voici ce qui compte vraiment pour l'examen et au-delà.

Recherche linéaire : la base

La recherche linéaire examine chaque élément d'une liste, un par un, jusqu'à trouver la cible ou atteindre la fin. C'est tout.

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

Dans le pire des cas, vous examinez chaque élément, donc c'est O(n). Dans le meilleur des cas, la cible est en première position, donc O(1). Les examinateurs aiment vous demander de déclarer les deux. La recherche linéaire fonctionne sur des données non triées, ce qui est son seul véritable avantage sur la recherche binaire.

Recherche binaire : celle qui trompe les gens

La recherche binaire ne fonctionne que sur une liste triée. Vous comparez la cible à l'élément du milieu. Si la cible est plus petite, vous éliminez la moitié supérieure ; si elle est plus grande, vous éliminez la moitié inférieure. Répétez jusqu'à ce que vous la trouviez ou que vous manquiez d'éléments.

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

C'est O(log n), ce qui la rend beaucoup plus rapide sur les grands ensembles de données. Cherchez dans une liste triée d'un million d'éléments et la recherche linéaire pourrait nécessiter jusqu'à un million de comparaisons ; la recherche binaire en nécessite environ 20. Les examinateurs vous donnent couramment une liste de, disons, 16 nombres et vous demandent de tracer les indices qui sont vérifiés — entraînez-vous à la main avec un crayon et du papier, pas seulement mentalement.

Tri à bulles : simple mais lent

Le tri à bulles parcourt répétitivement la liste en échangeant les éléments adjacents s'ils sont dans le mauvais ordre. Chaque passage complet pousse le plus grand élément non trié vers sa position correcte à la fin.

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

Le pire des cas est O(n²) — pour chaque élément, vous pourriez scanner presque toute la liste à nouveau. Il est rarement utilisé dans les vrais logiciels car il est lent sur les grandes données, mais les examinateurs l'aiment parce que le tracer à la main est gérable et montre clairement l'idée des passages et échanges répétés. Sachez comment compter le nombre de comparaisons et d'échanges dans un tableau de traces ; c'est un élément commun du barème de notation.

Tri fusion : diviser pour régner

Le tri fusion divise la liste en deux à plusieurs reprises jusqu'à ce que chaque sous-liste n'ait qu'un élément, puis fusionne ces sous-listes ensemble dans l'ordre trié.

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)

L'étape de fusion compare les premiers éléments de chaque moitié et choisit le plus petit, en répétant jusqu'à ce que les deux moitiés soient utilisées. Cela donne O(n log n), qui surpasse confortablement le tri à bulles sur tout sauf les très petites listes. Les questions de GCSE vous demandent parfois de dessiner le diagramme de division et fusion — une forme d'arbre montrant la liste se divisant et se recombinant. Entraînez-vous à dessiner cela pour une liste de 8 nombres afin d'être rapide dans les conditions d'examen.

Ce que les examinateurs testent réellement

La plupart des barèmes de notation vous demandent de pouvoir :

• Tracer un algorithme étape par étape et écrire l'état de la liste après chaque passage ou comparaison.
• Indiquer la complexité temporelle en termes Big O, ou du moins la décrire en mots (