Première · Numérique et sciences informatiques

Découvrir parcours, recherche et tri : trois familles d'algorithmes sur les tableaux

Distinguer parcours, recherche (linéaire et dichotomique) et tri par insertion sur un tableau, savoir dire ce que fait chacun et dans quel cas l'utiliser, puis le dérouler à la main sur un petit exemple.

Aperçu gratuit
Illustration de la fiche « Découvrir parcours, recherche et tri : trois familles d'algorithmes sur les tableaux »

Les points essentiels

  • Un parcours consiste à visiter les éléments d'un tableau un par un, en général avec une boucle for sur les indices ou sur les valeurs ; c'est la brique de base de presque tous les algorithmes de ce chapitre.
  • La recherche linéaire (séquentielle) parcourt le tableau du début à la fin et compare chaque élément à la valeur cherchée ; elle fonctionne sur un tableau trié ou non, et dans le pire cas elle effectue autant de comparaisons que d'éléments.

Les mots à connaître

Parcours séquentiel
Visite de tous les éléments d'un tableau dans l'ordre des indices 0, 1, ..., len(t)-1, par exemple avec for i in range(len(t)) ou for x in t.
Recherche dichotomique
Méthode de recherche dans un tableau trié qui divise à chaque étape par deux la zone de recherche en comparant la valeur cherchée à l'élément central.

Un exemple pour comprendre

On cherche la valeur 9 dans t = [4, 7, 2, 9, 5]. Déroule la recherche linéaire en donnant l'indice renvoyé et le nombre de comparaisons.

On parcourt dans l'ordre : i=0, t[0]=4 différent de 9 ; i=1, t[1]=7 différent de 9 ; i=2, t[2]=2 différent de 9 ; i=3, t[3]=9 égal à 9, on s'arrête. L'indice renvoyé est 3 et on a fait 4 comparaisons. Si la valeur cherchée avait été 8, on aurait parcouru les 5 éléments sans succès (5 comparaisons) et renvoyé -1 ou False. Le tableau n'étant pas trié, la dichotomie ne serait pas applicable ici.

Première page de l’Essentiel : Découvrir parcours, recherche et tri : trois familles d'algorithmes sur les tableaux
Ketty