Contrôle bientôt, chapitre jamais ouvert : le combo classique. Respire. Un algorithme, c'est juste une recette que l'ordinateur suit à la lettre, et ici on n'a que deux gestes à comprendre : chercher dans une liste, et ranger une liste. En dix minutes tu tiens l'essentiel.
Les 3 prérequis (rien de méchant)
Avant tout, trois mots à avoir en tête. C'est tout ce dont tu as besoin.
- Une variable : une boîte qui garde une valeur. On y range une valeur avec la flèche $\leftarrow$ (lire « reçoit »). Par exemple max $\leftarrow 7$ met $7$ dans la boîte max.
- Une liste $L$ : une suite de $n$ valeurs, dans des cases numérotées de $1$ à $n$. $L[i]$ désigne la valeur rangée dans la case numéro $i$ (l'indice).
- Une boucle « Pour i allant de a à b » : on répète une action en faisant avancer $i$, une case après l'autre.
- Une conditionnelle « Si … alors … » : on n'agit que si la condition est vraie.
Attention à ne pas confondre l'indice (le numéro de la case, $i$) et la valeur (ce qu'il y a dedans, $L[i]$). C'est le piège numéro un.
L'essentiel en une phrase
Chercher, c'est parcourir la liste pour en tirer une information : la plus grande valeur, ou savoir si une valeur donnée est présente. Trier, c'est réorganiser la liste dans l'ordre croissant.
La seule formule à retenir pour ton contrôle :
Pour trouver le maximum, l'idée tient en une image : tu prends la première case comme champion provisoire, puis tu compares le champion à chaque case suivante. Dès que tu tombes sur plus grand, tu as un nouveau champion.
Un exemple entièrement traité
Cherchons le maximum de la liste $[3,\;7,\;2,\;9,\;5]$ (donc $n=5$). On suit la méthode du champion.
Départ : max $\leftarrow L[1] = 3$. Le champion provisoire est $3$.
$i = 2$ : $L[2] = 7$. Est-ce que $7 > 3$ ? Oui, donc max devient $7$.
$i = 3$ : $L[3] = 2$. Est-ce que $2 > 7$ ? Non, max reste $7$.
$i = 4$ : $L[4] = 9$. Est-ce que $9 > 7$ ? Oui, donc max devient $9$.
$i = 5$ : $L[5] = 5$. Est-ce que $5 > 9$ ? Non, max reste $9$.
Résultat : le maximum est $9$. On a fait $4$ comparaisons, soit bien $n-1$ avec $n=5$.
La case en surbrillance ci-dessous est celle qui gagne à la fin. Retiens surtout le geste : on part de $L[1]$, jamais de $0$.
Les listes, les boucles, oui, ça revient. On reprend tout au propre, dans l'ordre, sans trou : les définitions, puis les deux recherches, puis le tri. À la fin tu sauras poser chaque algorithme et dire combien de comparaisons il coûte.
Définitions et boîte à outils
Un algorithme de recherche parcourt une liste pour en extraire une information : la valeur maximale, la position d'un élément, la présence d'une valeur… Un algorithme de tri réorganise les éléments d'une liste dans l'ordre croissant (ou décroissant).
Tous ces algorithmes se construisent avec les trois mêmes briques :
- des variables (des boîtes qui retiennent une valeur, mise à jour avec $\leftarrow$) ;
- des boucles (« Pour … » quand on connaît le nombre de tours, « Tant que … » sinon) ;
- des conditionnelles (« Si … alors … »).
Convention d'indices. Dans une liste de $n$ éléments, les indices vont de $1$ à $n$ : le premier élément est $L[1]$, le dernier est $L[n]$. (En Python, la numérotation commencera à $0$, mais gardons la convention du cours.)
Les deux recherches
Recherche du maximum. On initialise une variable max avec le premier élément, puis on parcourt le reste de la liste : dès qu'on rencontre un élément strictement plus grand, on met max à jour.
Pour i allant de 2 a n :
Si L[i] > max alors max ← L[i]
Retourner max
Cet algorithme effectue exactement $n-1$ comparaisons, quel que soit le contenu de la liste : la boucle démarre à $2$ et va jusqu'à $n$, donc $n-1$ tours, une comparaison par tour.
max $\leftarrow 6$. Puis $2 > 6$ ? non ; $9 > 6$ ? oui, max $= 9$ ; $4 > 9$ ? non.
Maximum $= 9$, en $3$ comparaisons.
Recherche d'un élément. On parcourt la liste et on signale si une valeur donnée est présente ou absente.
Pour i allant de 1 a n :
Si L[i] = valeur alors trouve ← Vrai
Retourner trouve
Meilleur cas : $1$ comparaison (l'élément est trouvé dès $L[1]$, si l'on s'arrête au premier succès). Pire cas : $n$ comparaisons (l'élément est absent, ou en dernière position, et il faut aller au bout de la liste).
Le tri par sélection
L'idée : à chaque étape, on cherche le plus petit élément de la partie non encore triée et on le met à sa place définitive, tout à gauche de cette partie. On répète en avançant la frontière d'une case vers la droite.
- Repérer la portion non triée : les indices $i$ à $n$.
- Trouver l'indice $i_{\min}$ du minimum de cette portion (boucle interne sur $j$ de $i+1$ à $n$).
- Échanger $L[i]$ et $L[i_{\min}]$ (même si $i_{\min} = i$, on écrit l'échange).
- Incrémenter $i$ et recommencer jusqu'à $i = n-1$.
imin ← i
Pour j allant de i+1 a n :
Si L[imin] > L[j] alors imin ← j
Echanger L[i] et L[imin]
Retourner L
Dans le pseudo-code, on garde $i_{\min}$ (noté imin), l'indice du plus petit trouvé jusque-là ; $L[\text{imin}]$ est la valeur à cet indice. La condition « $L[\text{imin}] > L[j]$ » se lit : « le minimum courant est plus grand que $L[j]$ », donc $L[j]$ devient le nouveau minimum.
On sort le brouillon et on déroule ensemble, ligne par ligne. Tu ne fais rien seul ici : on regarde le film au ralenti, chaque comparaison est commentée. Le but, c'est que le geste devienne un réflexe.
Ensemble : le maximum de $[8,\;3,\;11,\;6]$
On applique le pseudo-code de la recherche du maximum, en écrivant à chaque ligne ce que vaut la variable max.
Ligne max $\leftarrow L[1]$ : la première case vaut $8$, donc max $= 8$.
Tour $i = 2$ : on lit $L[2] = 3$. Test $3 > 8$ ? Faux. On ne touche à rien, max reste $8$.
Tour $i = 3$ : on lit $L[3] = 11$. Test $11 > 8$ ? Vrai. On exécute max $\leftarrow 11$.
Tour $i = 4$ : on lit $L[4] = 6$. Test $6 > 11$ ? Faux. max reste $11$.
La boucle est finie (on est allé jusqu'à $i = n = 4$). On retourne max $= 11$.
Compte des comparaisons : une par tour, de $i=2$ à $i=4$, soit $3 = n-1$. C'est toujours le cas, même si le maximum était en première position.
Ensemble : l'élément est-il là ?
On cherche d'abord la valeur $7$ dans $[4,\;7,\;1,\;9]$, puis la valeur $5$ dans la même liste. On suit le pseudo-code de la recherche d'un élément.
trouvé $\leftarrow$ Faux au départ.
$i=1$ : $L[1]=4$. Est-ce $4 = 7$ ? Non.
$i=2$ : $L[2]=7$. Est-ce $7 = 7$ ? Oui, donc trouvé $\leftarrow$ Vrai.
$i=3$ puis $i=4$ : $1=7$ ? non ; $9=7$ ? non. trouvé reste Vrai.
On retourne Vrai : la valeur est présente.
trouvé $\leftarrow$ Faux.
$i=1$ à $i=4$ : $4=5$ ? non ; $7=5$ ? non ; $1=5$ ? non ; $9=5$ ? non.
trouvé n'a jamais changé : on retourne Faux. Il a fallu $4 = n$ comparaisons (pire cas).
Remarque utile : la version « Pour » ci-dessus parcourt toute la liste même après avoir trouvé. Si on veut s'arrêter dès le premier succès (et retomber sur le « meilleur cas $= 1$ comparaison »), on remplace la boucle par un « Tant que non trouvé et $i \leq n$ ». On y reviendra au palier suivant.
Ensemble : tri par sélection de $[4,\;1,\;3,\;2]$
Le grand classique. On trie $[4,\;1,\;3,\;2]$ ($n=4$) en détaillant chaque comparaison de la boucle interne. La frontière $i$ avance de $1$ à $n-1 = 3$.
imin $\leftarrow 1$ (on part du premier : candidat $L[1]=4$).
$j=2$ : $L[1]=4$ plus grand que $L[2]=1$ ? Oui, donc imin $\leftarrow 2$ (min courant $=1$).
$j=3$ : $L[2]=1$ plus grand que $L[3]=3$ ? Non. $j=4$ : $1$ plus grand que $L[4]=2$ ? Non.
imin $=2$. On échange $L[1]$ et $L[2]$ : la liste devient $[\mathbf{1},\;4,\;3,\;2]$. (3 comparaisons)
imin $\leftarrow 2$ (candidat $L[2]=4$).
$j=3$ : $4$ plus grand que $3$ ? Oui, imin $\leftarrow 3$. $j=4$ : $3$ plus grand que $2$ ? Oui, imin $\leftarrow 4$.
imin $=4$. On échange $L[2]$ et $L[4]$ : $[1,\;\mathbf{2},\;3,\;4]$. (2 comparaisons)
imin $\leftarrow 3$ (candidat $L[3]=3$). $j=4$ : $3$ plus grand que $4$ ? Non.
imin $=3$ : le minimum est déjà en place. On écrit quand même l'échange $L[3]$ avec $L[3]$ : $[1,\;2,\;\mathbf{3},\;4]$. (1 comparaison)
Liste triée : $[1,\;2,\;3,\;4]$. Nombre total de comparaisons : $3+2+1 = 6$.
Niveau contrôle maintenant. Le correcteur ne note pas ta bonne volonté, il note ta rigueur : le bon départ, le bon compte de comparaisons, l'échange qu'on oublie une fois sur deux. On blinde tout, avec un problème type entièrement résolu et la liste des pièges où tout le monde tombe.
Compter les comparaisons (ce que le correcteur adore)
Une question quasi systématique : « combien de comparaisons ? ». Voici les trois résultats à connaître par cœur.
Le tri par sélection fait une passe pour chaque $i$ de $1$ à $n-1$ ; la passe $i$ compare $n-i$ éléments. En additionnant, on retrouve la somme $1+2+\dots+(n-1)$. Pour $n=4$, cela donne bien $3+2+1=6$ ; pour $n=6$, cela donne $5+4+3+2+1 = 15 = \dfrac{6\times 5}{2}$.
Un problème type entièrement résolu
Énoncé. On donne la liste $L = [5,\;2,\;8,\;2,\;1]$. Applique le tri par sélection : écris la liste après chaque échange et donne le nombre total de comparaisons. (Attention, il y a deux fois la valeur $2$.)
Minimum de la portion : $1$, à l'indice $5$. On échange $L[1]$ et $L[5]$.
$\rightarrow [\mathbf{1},\;2,\;8,\;2,\;5]$. (4 comparaisons)
Minimum : $2$. La première occurrence est déjà à l'indice $2$ (la condition est stricte, on ne bouge pas sur une égalité). imin $= 2$.
On échange $L[2]$ avec lui-même $\rightarrow [1,\;\mathbf{2},\;8,\;2,\;5]$. (3 comparaisons)
Minimum : $2$, à l'indice $4$. On échange $L[3]$ et $L[4]$.
$\rightarrow [1,\;2,\;\mathbf{2},\;8,\;5]$. (2 comparaisons)
Minimum : $5$, à l'indice $5$. On échange $L[4]$ et $L[5]$.
$\rightarrow [1,\;2,\;2,\;\mathbf{5},\;8]$. (1 comparaison)
Liste triée : $[1,\;2,\;2,\;5,\;8]$. Total : $4+3+2+1 = 10$ comparaisons, ce qui vaut bien $\dfrac{n(n-1)}{2} = \dfrac{5\times 4}{2} = 10$. Les doublons ne posent aucun problème.
Pièges classiques et attentes du correcteur
- Initialiser max $\leftarrow 0$ au lieu de max $\leftarrow L[1]$ : faux dès que tous les éléments sont négatifs (le maximum de $[-3,-8,-2]$ n'est pas $0$).
- Confondre indice et valeur : $i_{\min}$ est un indice, $L[i_{\min}]$ est la valeur à cet indice.
- Oublier l'échange dans le tri : mémoriser l'indice du minimum ne suffit pas, il faut vraiment permuter $L[i]$ et $L[i_{\min}]$.
- Démarrer la boucle du maximum à $i=1$ au lieu de $i=2$ : on compare alors $L[1]$ avec lui-même, comparaison inutile.
- un pseudo-code propre : initialisation correcte, bonnes bornes de boucle, indentation lisible ;
- la trace demandée : la valeur des variables (ou la liste) à chaque étape, pas seulement le résultat final ;
- le décompte des comparaisons, avec la justification ($n-1$, ou la somme $\tfrac{n(n-1)}{2}$) ;
- distinguer meilleur cas et pire cas quand c'est demandé (recherche d'un élément).
Le programme est plié, mais la vraie question arrive : peut-on chercher plus vite ? Et pourquoi ces comptes de comparaisons tombent-ils toujours juste ? Petit coup d'œil par-dessus la clôture, vers l'an prochain, sans rien qui soit exigible au contrôle.
Justifier les comptes (idée de démonstration)
Les formules $n-1$ et $\dfrac{n(n-1)}{2}$ ne sortent pas d'un chapeau. On peut les justifier proprement, et c'est un bon entraînement au raisonnement.
Pour le maximum : chacun des éléments, sauf le premier (qui sert de champion de départ), est comparé exactement une fois à max. Il y a $n-1$ autres éléments, donc $n-1$ comparaisons. Rien ne dépend des valeurs.
Pour le tri par sélection : il faut sommer $1+2+\dots+(n-1)$. L'astuce de Gauss : on écrit la somme à l'endroit et à l'envers, et on additionne terme à terme.
En pratique : les paires $(1,\,n-1),\,(2,\,n-2),\dots$ valent toutes $n$ en s'associant, d'où le résultat. C'est exactement le genre de somme que tu manipuleras avec les suites arithmétiques.
Ouverture : chercher dans une liste déjà triée
La recherche vue en cours est séquentielle : on regarde les cases une à une, jusqu'à $n$ comparaisons. Mais si la liste est déjà triée, on peut faire beaucoup mieux avec la recherche dichotomique : on regarde l'élément du milieu, et selon qu'il est trop grand ou trop petit, on jette la moitié de la liste. À chaque comparaison, on divise le travail par deux.
Milieu (indice $4$) : $9$. Est-ce que $12$ est plus grand que $9$ ? Oui, on ne garde que la moitié droite (indices $5$ à $7$).
Milieu de cette moitié (indice $6$) : $15$. Est-ce que $12$ est plus petit que $15$ ? Oui, on ne garde que l'indice $5$.
Indice $5$ : $12$. Trouvé, en $3$ comparaisons au lieu de $7$.
L'ordre de grandeur passe de $n$ comparaisons à environ $\log_2(n)$ : pour un million d'éléments, on tombe de $10^6$ à une vingtaine de tests. D'où l'idée forte : trier d'abord coûte cher une fois, mais rend ensuite chaque recherche quasi instantanée.
Vers la Première, la Terminale (et Python)
Ces algorithmes sont la porte d'entrée d'un thème central : le coût d'un algorithme, ou complexité. Tu compareras alors des ordres de grandeur : le tri par sélection coûte de l'ordre de $n^2$ opérations (les deux boucles imbriquées), quand d'autres tris atteignent $n\log_2(n)$, bien plus rapide sur de grandes listes.
- Liens avec le reste du programme : les boucles imbriquées et les fonctions que tu retrouves dans tous les scripts ; les suites arithmétiques pour les sommes de comparaisons.
- D'autres tris apparaîtront (comme le tri par insertion), avec la même démarche : décrire, tracer, compter.
- En Python, tout cela est déjà emballé : max(L), valeur in L, sorted(L) font en une ligne ce qu'on a écrit à la main. Savoir ce qu'il y a dessous, c'est justement l'objet de ce chapitre.
Autrement dit, tu ne réécriras pas ces algorithmes toute ta vie, mais comprendre comment et à quel coût une machine cherche et range, c'est le socle de toute l'informatique qui suit.