Vérifier un par un
Recherche linéaire : vérifier chaque élément
Imaginez que vous ayez 10 cartes face cachée, numérotées de 1 à 10, mélangées dans un ordre aléatoire.
Vous voulez trouver la carte avec le chiffre 7.
Vous retournez les cartes une par une, de gauche à droite, jusqu'à ce que vous la trouviez.
| Scénario | Retournements nécessaires |
|---|---|
| Meilleur cas | 1 retournement (premier essai chanceux !) |
| Pire cas | 10 retournements (c'était la dernière carte) |
| Moyenne | environ 5 retournements |
Imaginez maintenant 100 cartes. Moyenne : environ 50 retournements.
1 000 cartes ? Moyenne : environ 500 retournements.
Voyez le modèle ? Deux fois plus de cartes, deux fois plus de travail. Le travail croît en ligne droite.
Les informaticiens appellent cela la recherche linéaire — linéaire signifie que le travail croît comme une ligne : régulier et prévisible.
La recherche linéaire fonctionne sur TOUTE liste, triée ou non. Cela la rend simple. Mais elle peut devenir lente.
Combien de noms ?
Vous avez une liste de classe de 20 noms écrite dans un ordre aléatoire.
Vous devez trouver le nom Zoe.
Vous vérifiez les noms un par un, du haut de la liste vers le bas.
Couper la liste en deux
Recherche binaire : sauter au milieu
La recherche binaire a une règle : la liste doit d'abord être triée.
Si votre liste de 20 noms va de A à Z, vous pouvez utiliser la recherche binaire.
Comment ça marche : ouvrez au nom du milieu (nom n°10). Demandez-vous : Zoe est-il avant ou après ce nom ?
Z vient près de la fin de l'alphabet, donc Zoe vient APRÈS le milieu. Jetez la première moitié. Maintenant vous n'avez que les noms 11-20.
Vérifiez le milieu de ces 10 noms (nom n°15). Z vient après M, donc Zoe vient après le nom n°15. Jetez les noms 11-14. Maintenant vous avez les noms 16-20.
Continuez à couper en deux. Chaque vérification supprime la moitié des noms restants.
| Taille de la liste | Vérifications maximales avec recherche binaire |
|---|---|
| 20 noms | au maximum 5 vérifications |
| 1 000 noms | au maximum 10 vérifications |
| 1 000 000 noms | au maximum 20 vérifications |
Comparez cela à la recherche linéaire sur 1 000 000 de noms : une moyenne de 500 000 vérifications.
La recherche binaire coupe la liste en deux à chaque fois. Couper en deux à plusieurs reprises atteint 1 très rapidement — c'est pourquoi elle reste si rapide.
Trouver « figue » dans une liste triée
Voici une liste triée de 8 mots :
1. pomme 2. banane 3. cerise 4. datte 5. baie de sureau 6. figue 7. raisin 8. melon miel
Vous voulez trouver figue en utilisant la recherche binaire.
Rappelez-vous : vérifiez le milieu, demandez-vous si votre cible vient avant ou après, puis coupez la liste en deux.
Échanger les voisins dans l'ordre
Tri à bulles : comparer les voisins et échanger
Le tri à bulles met une liste en ordre en comparant deux éléments voisins à la fois.
Si deux voisins sont dans le désordre — échangez-les.
Continuez à faire des passages dans la liste jusqu'à ce que rien ne nécessite d'échange.
Exemple : trier [5, 3, 8, 1]
Passage 1 :
- Comparez 5 et 3. 5 > 3, donc échangez → [3, 5, 8, 1]
- Comparez 5 et 8. 5 < 8, pas d'échange → [3, 5, 8, 1]
- Comparez 8 et 1. 8 > 1, donc échangez → [3, 5, 1, 8]
Passage 2 :
- Comparez 3 et 5. OK → [3, 5, 1, 8]
- Comparez 5 et 1. 5 > 1, échangez → [3, 1, 5, 8]
- Comparez 5 et 8. OK → [3, 1, 5, 8]
Passage 3 :
- Comparez 3 et 1. 3 > 1, échangez → [1, 3, 5, 8]
- Comparez 3 et 5. OK. Comparez 5 et 8. OK.
Fait ! [1, 3, 5, 8] ✓
Remarque : le plus grand nombre « remonte » à la fin de la liste à chaque passage. C'est ainsi que le tri à bulles tire son nom.
Le tri à bulles fonctionne. Ce n'est pas le plus rapide pour les grandes listes, mais c'est facile à comprendre — parfait pour apprendre.
Trier [4, 2, 7, 1] avec le tri à bulles
Triez cette liste en utilisant le tri à bulles : [4, 2, 7, 1]
Montrez la liste après chaque passage. Comptez combien de passages il faut pour terminer.