Algorithmes de recherche et tri simple

Les prérequis indispensables

Avant de plonger dans les algorithmes, on remet en place les briques de base que tout programme utilise.

Une variable : c'est comme une boîte qui porte un nom et qui contient une valeur (un nombre, un mot, vrai/faux...). On peut lire ce qu'il y a dedans, et on peut changer son contenu. Exemple : max ← 7 signifie qu'on met la valeur 7 dans la boîte nommée max.

Une liste : c'est une collection d'éléments rangés dans un ordre précis. Chaque élément a une position, qu'on appelle son indice. En pseudo-code, les indices commencent à 1. Par exemple, dans la liste L = [7, 2, 9], l'élément à l'indice 1 est 7, à l'indice 2 c'est 2, à l'indice 3 c'est 9.

Une boucle : c'est une structure qui répète un bloc d'instructions plusieurs fois. La boucle Pour i allant de 2 à n signifie qu'on va exécuter le bloc pour i = 2, puis i = 3, ..., jusqu'à i = n. La boucle Tant que répète tant qu'une condition est vraie.

Une conditionnelle : c'est un test qui permet de choisir entre deux actions. Si condition alors instruction exécute l'instruction seulement si la condition est vraie.

Recherche du maximum : l'essentiel

On a une liste de nombres. On veut trouver le plus grand. L'idée est simple : on prend le premier comme champion provisoire, puis on le compare à chacun des suivants. Dès qu'on en trouve un plus grand, il devient le nouveau champion. À la fin, le champion est le maximum de toute la liste.

Pseudo-code :

max ← L[1]
Pour i allant de 2 à n :
    Si L[i] > max alors
        max ← L[i]
Retourner max

Le nombre de comparaisons est toujours exactement n - 1, car on compare chaque élément (sauf le premier) au maximum courant.

Recherche d'un élément : l'essentiel

On veut savoir si une valeur précise est présente dans la liste. On parcourt la liste du début à la fin. Dès qu'on trouve la valeur, on peut s'arrêter et dire qu'elle est là. Si on arrive au bout sans l'avoir trouvée, elle n'y est pas.

Pseudo-code :

trouvé ← Faux
Pour i allant de 1 à n :
    Si L[i] = valeur alors
        trouvé ← Vrai
Retourner trouvé

Le nombre de comparaisons dépend de la position de l'élément cherché. Meilleur cas : 1 comparaison (l'élément est au début). Pire cas : n comparaisons (l'élément est absent ou tout à la fin).

Méthode pas-à-pas : recherche du maximum

Pour appliquer l'algorithme de recherche du maximum à une liste $L$ de $n$ éléments :

1. Initialiser la variable $max$ avec le premier élément : $max \leftarrow L[1]$.
2. Parcourir les indices $i$ de 2 à $n$ avec une boucle Pour.
3. Pour chaque $i$, comparer $L[i]$ et $max$ : si $L[i] > max$, alors mettre à jour $max \leftarrow L[i]$.
4. À la fin de la boucle, retourner $max$.

Piège à éviter : ne jamais initialiser $max$ à 0. Si tous les éléments sont négatifs, 0 serait plus grand qu'eux, et le résultat serait faux. On initialise toujours avec $L[1]$.

Méthode pas-à-pas : recherche d'un élément

Pour savoir si une valeur $v$ est dans la liste $L$ :

1. Initialiser une variable booléenne $trouvé$ à Faux.
2. Parcourir les indices $i$ de 1 à $n$ avec une boucle Pour.
3. Pour chaque $i$, comparer $L[i]$ et $v$ : si $L[i] = v$, alors $trouvé \leftarrow$ Vrai.
4. À la fin de la boucle, retourner $trouvé$.

Le nombre de comparaisons varie : 1 si l'élément est en première position, $n$ s'il est absent ou en dernière position.

Tri par sélection : principe et méthode

Le tri par sélection range une liste dans l'ordre croissant. L'idée : à chaque étape, on sélectionne le plus petit élément de la partie encore non triée, et on le place au début de cette partie.

Méthode pas-à-pas :

1. Pour $i$ allant de 1 à $n-1$ :
   • La partie non triée est constituée des indices $i$ à $n$.
   • On cherche l'indice $i_{\min}$ du minimum dans cette partie (boucle interne sur $j$ de $i+1$ à $n$).
   • On échange $L[i]$ et $L[i_{\min}]$ (même si $i_{\min} = i$, auquel cas l'échange ne change rien).
2. Après $n-1$ étapes, la liste est entièrement triée.

Erreur fréquente : confondre l'indice du minimum et sa valeur. $i_{\min}$ est un numéro de position, $L[i_{\min}]$ est la valeur à cette position. Pour l'échange, on utilise les indices, pas les valeurs.

Rappel : sens direct et réciproque en algorithmique

En algorithmique de recherche, on peut voir deux directions :

• Trouver une valeur (le maximum, un élément) : on parcourt la liste et on extrait une information. C'est le sens direct de la recherche.
• Trier une liste : on réorganise les éléments pour qu'ils soient dans un certain ordre. C'est une opération plus lourde, qui prépare le terrain pour d'autres recherches plus efficaces (comme la recherche dichotomique, que tu verras plus tard).

Le tri par sélection est un tri simple mais coûteux en nombre de comparaisons : pour une liste de $n$ éléments, il effectue toujours $\frac{(n-1)n}{2}$ comparaisons, soit environ $n^2/2$.

Complexité : un aperçu

La complexité d'un algorithme mesure son efficacité en temps (ou en mémoire) quand la taille des données augmente. On l'exprime souvent en fonction de $n$, le nombre d'éléments.

• Recherche du maximum : $n-1$ comparaisons, soit une complexité linéaire (proportionnelle à $n$).
• Recherche d'un élément : entre 1 et $n$ comparaisons, complexité linéaire en pire cas.
• Tri par sélection : environ $n^2/2$ comparaisons, soit une complexité quadratique (proportionnelle à $n^2$). Pour $n=1000$, cela fait environ 500 000 comparaisons.

Quand on double la taille de la liste, un algorithme linéaire prend environ 2 fois plus de temps ; un algorithme quadratique prend environ 4 fois plus de temps. C'est pour cela que pour de grandes listes, on préfère des algorithmes de tri plus rapides (comme le tri fusion, que tu verras en 1ère).

Recherche dichotomique : l'idée

Quand une liste est triée, on peut chercher un élément beaucoup plus vite. Au lieu de parcourir du début à la fin, on compare l'élément cherché avec le milieu de la liste. S'il est plus petit, on cherche dans la moitié gauche ; s'il est plus grand, dans la moitié droite. On répète jusqu'à trouver ou jusqu'à ce que la zone de recherche soit vide.

Cet algorithme s'appelle la recherche dichotomique (du grec "dichotomia", couper en deux). Sa complexité est logarithmique : pour une liste de $n$ éléments, il faut environ $\log_2(n)$ comparaisons. Pour $n=1000$, $\log_2(1000) \approx 10$ comparaisons, contre 1000 en recherche linéaire. C'est colossal !