Objectifs

Décrire une recherche et un tri simples, compter des comparaisons et vérifier des cas limites.

Décrire une recherche précise

Un algorithme est une suite finie d’instructions précises pour résoudre un problème. On fixe ses entrées, le résultat attendu et les conditions d’arrêt. Pour une recherche séquentielle, on examine chaque valeur dans l’ordre jusqu’à trouver la cible ou atteindre la fin.

Liste fictive : 300, 700, 500, 900. Cible : 500. Combien de comparaisons avec la cible faut-il ?

flowchart LR
A[Debut] --> B[Valeur suivante]
B --> C{Egale a la cible}
C -->|Oui| D[Trouvee et arret]
C -->|Non| E{Fin de liste}
E -->|Oui| F[Absente et arret]
E -->|Non| B

Compter et tester

La complexité décrit comment le travail nécessaire évolue avec la taille des données. Pour la recherche séquentielle dans une liste de \(n\) valeurs, on compte ici une comparaison avec la cible par valeur examinée. Le meilleur cas demande une comparaison ; le pire cas en demande \(n\), si la cible est absente ou trouvée à la fin.

Teste la méthode sur une liste vide, une cible en tête, une cible en fin, une cible absente et des valeurs répétées. Un test révèle des erreurs, mais quelques essais réussis ne prouvent pas à eux seuls tous les cas.

Trier avant de rechercher autrement

Le tri par sélection cherche le plus petit élément de la partie non triée et l’échange avec la première place de cette partie. On recommence sur la suite. Après chaque passage, les premières places contiennent les plus petites valeurs dans l’ordre : cette propriété explique pourquoi la méthode est correcte.

Trie la liste fictive 8, 3, 5, 1 par sélection.

Pour \(n\) valeurs, cette version du tri par sélection effectue \[\frac{n(n-1)}{2}\] comparaisons pour trouver les minima. La somme vient des passages successifs : le premier compare les autres valeurs au minimum provisoire, puis la zone non triée diminue.

Sur une liste déjà triée, la recherche dichotomique compare à une valeur du milieu et élimine la moitié inutile, puis recommence. Sans tri préalable, on risque d’écarter la cible.

Récapitulatif

Définis entrée et sortie, prévois l’arrêt, teste les cas limites et précise quelle opération tu comptes avant de comparer les méthodes.