Algorithmes de recherche et tri simple
Un algorithme de recherche parcourt une liste pour en extraire une information : la valeur maximale, la position d'un élément donné, etc. Un algorithme de tri réorganise les éléments d'une liste dans l'ordre croissant (ou décroissant).
Ces algorithmes combinent trois structures fondamentales : variables, boucles (Pour, Tant que) et conditionnelles (Si … alors). En pseudo-code, les indices d'une liste de $n$ éléments vont de $1$ à $n$.
On initialise une variable max avec le premier élément, puis on parcourt le reste de la liste : dès qu'on trouve un élément strictement plus grand, on met max à jour.
Pseudo-code :
max ← L[1]
Pour i allant de 2 à n :
Si L[i] > max alors max ← L[i]
Retourner max
L'algorithme effectue exactement $n - 1$ comparaisons, quel que soit le contenu de la liste.
On parcourt la liste et on signale si un élément de valeur donnée est présent ou absent.
Pseudo-code :
trouvé ← Faux
Pour i allant de 1 à n :
Si L[i] = valeur alors trouvé ← Vrai
Retourner trouvé
Meilleur cas : 1 comparaison (élément en L[1]). Pire cas : $n$ comparaisons (élément absent ou en dernière position).
- Repérer la portion non triée : 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$).
- Incrémenter $i$ et recommencer jusqu'à $i = n - 1$.
- Initialiser max ← 0 au lieu de max ← L[1] : incorrect si tous les éléments sont négatifs.
- Confondre indice et valeur : $i_{\min}$ est un indice, $L[i_{\min}]$ est la valeur à cet indice.
- Oublier l'échange dans le tri par sélection et se contenter de mémoriser l'indice du minimum.
- Démarrer la boucle à $i = 1$ au lieu de $i = 2$ dans la recherche du maximum : on compare L[1] avec lui-même.