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élangé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 (première chance lucky !) |
| 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 ? Doubliez les 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. Cela le rend simple. Mais il peut être 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, de haut en bas de la liste.
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 ceux-ci (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.
Continuez à couper en deux. Chaque vérification élimine la moitié des noms restants.
Taille de la liste | Vérifications max 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. date 5. baie à vieillie 6. figue 7. raisin 8. melon
Vous souhaitez trouver figue à l'aide de 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 & échanger
Le tri du 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:
- Comparez 5 & 3. 5 > 3, donc échangez → [3, 5, 8, 1]
- Comparez 5 & 8. 5 < 8, pas d'échange → [3, 5, 8, 1]
- Comparez 8 & 1. 8 > 1, donc échangez → [3, 5, 1, 8]
Passage 2:
- Comparez 3 & 5. OK → [3, 5, 1, 8]
- Comparez 5 & 1. 5 > 1, échangez → [3, 1, 5, 8]
- Comparez 5 & 8. OK → [3, 1, 5, 8]
Passage 3:
- Comparez 3 & 1. 3 > 1, échangez → [1, 3, 5, 8]
- Comparez 3 & 5. OK. Comparez 5 & 8. OK.
Fini ! [1, 3, 5, 8] ✓
Attention : le plus grand nombre remonte en bulle à la fin de la liste à chaque passage. C'est ainsi que le tri du bulle tire son nom.
Le tri du bulle fonctionne. Il n'est pas le plus rapide pour les grandes listes, mais il est facile à comprendre - parfait pour l'apprentissage.
Trier [4, 2, 7, 1] avec Tri du Bulle
Triez cette liste à l'aide du tri du bulle : [4, 2, 7, 1]
Montrez la liste après chaque passage. Comptez combien de passes il faut pour terminer.