Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algorithmes sur les tableaux

Déjà plus de

1 million

d'inscrits !

Parcours séquentiel de liste

  • Le parcours séquentiel donne un accès individuel aux éléments d’une structure donnée, en les parcourant un par un et dans l’ordre.
  • Le parcours séquentiel d’une liste s’effectue avec une boucle de type for … in .

Recherche d’occurrence(s)

  • La recherche d’occurrence, dans une liste non triée, s’effectue en comparant chaque élément de la liste à l’élément recherché, jusqu’à le trouver ou jusqu’à atteindre la fin de la liste.
  • La recherche d’occurrence fonctionne aussi avec des types de données tels que :
  • une liste de nombres ;
  • des chaînes de caractères ;
  • des booléens ;
  • un tuple de tuples.
  • Si l’on veut rechercher toutes les occurrences, il faut parcourir l’intégralité de la liste.

Recherche d’extremums

  • Nous pouvons retourner simultanément le minimum et le maximum d’une liste d’éléments.
  • Si les listes ne sont pas triées, la recherche d’extremums nous oblige à les parcourir en totalité.
  • La recherche d’extremums fonctionne aussi avec des types de données tels que :
  • une liste de nombres ;
  • des chaînes de caractères ;
  • des booléens ;
  • un tuple de tuples.

Calcul de moyenne

  • Le calcul de la moyenne est assez proche de la recherche d’extremums, et nous oblige à nouveau à parcourir l’intégralité des éléments de la liste.
  • Mais il n’est pas possible de calculer la moyenne d’une liste de chaines de caractères, cette notion mathématique n’ayant pas de sens pour ce type de donnée.

Coût algorithmique

  • Pour un nombre nn d’éléments dans la liste, on parcourt au plus nn éléments.
  • Le coût algorithmique des recherches séquentielles est linéaire, de l’ordre de nn, noté O(n)\text{O}(n).

Tri par sélection

Principe du tri par sélection

  • Le tri par sélection repose sur des comparaisons et des échanges de positions dans la liste.
  • À l’issue du traitement, la liste est entièrement triée.

Implémentation

L’implémentation du tri par sélection repose sur l’imbrication de deux boucles :

  • la boucle extérieure parcourt la liste séquentiellement ;
  • la boucle intérieure parcourt la portion de liste restante pour en déterminer le minimum.

Terminaison et complexité

  • L’algorithme est composé de deux boucles for … in imbriquées.
  • Chacune de ces boucles se terminera car les itérations de type for ou for … in ne peuvent pas produire de boucles infinies.
  • Les boucles étant imbriquées le coût est quadratique. La complexité du tri par sélection est O(n2)\text{O}(n^{2}).

Tri par insertion

Principe du tri par insertion

  • Le principe du tri par insertion est analogue à celui du tri d’un jeu de cartes. Cette méthode assez intuitive permet de trier simplement et rapidement, un paquet de cartes par exemple.

Terminaison et complexité

  • L’algorithme est composé de deux boucles imbriquées :
  • la boucle externe for … in se terminera à l’épuisement des éléments de la liste ;
  • dans la boucle interne de type while, la variable j est un variant de boucle décroissant à chaque tour jusqu’à devenir nul.
  • Le coût est quadratique, la complexité temporelle de l’algorithme de tri par insertion est O(n2)\text{O}(n^{2}).
  • La performance du tri par sélection est meilleure quand les données sont presque triées ou quand le nombre de données à trier reste modéré.
  • Pour la recherche dichotomique le coût est réduit mais requiert en entrée une liste ordonnée.