Vérifier un à la fois
Recherche linéaire : vérifier chaque un
Imaginez que vous avez 10 cartes face cachées, numérotées de 1 à 10, mélangeées dans n'importe quel ordre.
Vous voulez trouver la carte avec le numéro 7.
Vous retournez les cartes les unes après les autres, de gauche à droite, jusqu'à la trouver.
| Scénario | Retours nécessaires |
|----------|-------------------|
| Meilleur cas | 1 retour (essai chanceux !) |
| Pire cas | 10 retours (c'était la dernière carte) |
| Moyenne | environ 5 retours |
Maintenant, imaginez 100 cartes. Moyenne : environ 50 retours.
1 000 cartes ? Moyenne : environ 500 retours.
Voyez le modèle ? Doublez le nombre de cartes, doublez le travail. Le travail augmente en ligne droite.
Les informaticiens appellent cela une recherche linéaire - linéaire signifie que le travail augmente comme une ligne : stable et prévisible.
La recherche linéaire fonctionne sur TOUTE liste, triée ou non. Ce qui le rend simple. Mais il peut devenir lent.
Combien de noms ?
Vous avez une liste de classe de 20 noms écrits dans n'importe quel ordre.
Vous devez trouver le nom Zoe.
Vous vérifiez les noms les uns après les autres, depuis le haut de la liste vers le bas.
Couper la liste en deux
Recherche binaire : sautez au milieu
La recherche binaire a une règle : la liste doit être triée en premier.
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 #10). Demandez : est-ce que Zoe vient avant ou après ce nom ?
Z vient vers la fin de l'alphabet, donc Zoe vient APRÈS le milieu. Jetez la première moitié. Vous n'avez maintenant plus que les noms 11-20.
Vérifiez le milieu de ces 10 noms (nom #15). Z vient après M, donc Zoe vient après le nom #15. Jetez les noms 11-14. Vous n'avez maintenant plus les noms 16-20.
Coupez en deux à chaque étape. Chaque vérification élimine la moitié des noms restants.
Taille de la liste | Nombre maximum de vérifications avec recherche binaire |
|-----------|-------------------------------|
| 20 noms | au plus 5 vérifications |
| 1 000 noms | au plus 10 vérifications |
| 1 000 000 noms | au plus 20 vérifications |
Comparez cela à la recherche linéaire sur 1 000 000 de noms : en moyenne, 500 000 vérifications.
La recherche binaire coupe la liste en deux à chaque fois. Couper en deux à plusieurs reprises atteint rapidement 1 - c'est pourquoi elle reste rapide.
Trouver 'fig' dans une liste triée
Voici une liste triée de 8 mots :
1. pomme 2. banane 3. cerise 4. datte 5. baie à vieillie 6. figue 7. raisin 8. melon
Vous souhaitez trouver fig en utilisant la recherche binaire.
Rappelez-vous : vérifiez le milieu, demandez si votre cible vient avant ou après, puis coupez la liste en deux.
Échange des voisins dans l'ordre
Trie par bulles : comparer les voisins et échanger
Le tri par bulle met une liste dans l'ordre en comparant deux items voisins à la fois.
Si deux voisins sont désordonnés - échangez-les.
Continuez à faire des passes à travers la liste jusqu'à ce qu'il n'y ait plus besoin d'échanger.
Exemple : trier [5, 3, 8, 1]
Passage 1:
- Compare 5 & 3. 5 > 3, donc échangez → [3, 5, 8, 1]
- Compare 5 & 8. 5 < 8, pas d'échange → [3, 5, 8, 1]
- Compare 8 & 1. 8 > 1, donc échangez → [3, 5, 1, 8]
Passage 2:
- Compare 3 & 5. OK → [3, 5, 1, 8]
- Compare 5 & 1. 5 > 1, échangez → [3, 1, 5, 8]
- Compare 5 & 8. OK → [3, 1, 5, 8]
Passage 3:
- Compare 3 & 1. 3 > 1, échangez → [1, 3, 5, 8]
- Compare 3 & 5. OK. Compare 5 & 8. OK.
Fini ! [1, 3, 5, 8] ✓
Attention : le plus grand nombre remonte à la fin de la liste à chaque passe. C'est ainsi que le tri par bulle tire son nom.
Le tri par bulle fonctionne. Ce n'est pas le plus rapide pour de grandes listes, mais c'est facile à comprendre - parfait pour l'apprentissage.
Trier [4, 2, 7, 1] avec Tri par Bulle
Triez cette liste à l'aide du tri par bulle : [4, 2, 7, 1]
Montrez la liste après chaque passe. Comptez combien de passes il faut pour terminer.