Les algorithmes de tri


Variations autour des tableaux

Insertion dans un tableau par recopie

En informatique, nous avons vu quun tableau est une structure de donnée de taille fixe. Mais dans de nombreuses situations, on peut souhaiter vouloir ajouter des éléments à un tableau.

Avec limplémentation des tableaux en python, nous avons déjà vu la possibilité dutiliser append(valeur) pour ajouter un élément à la fin dun tableau (et augmenter sa taille dune unité). Il existe aussi une autre fonction: insert(indice, valeur) qui comme son nom lindique insère une nouvelle valeur à la position dindice donné, en décallant toutes les valeurs situées plus à droite pour faire de la place.

Étudions à présent cet algorithme dun peu plus près, en écrivant nous même une fonction similaire à celle existant déjà en python.

def insertion_copie(tableau, indice, valeur):
   """
   Insère la 'valeur' à la position donné par 'indice' dans le tableau. 
   On doit nécessairement avoir 0 <= indice <= len(tableau) sous peine
   de déclencher une erreur. Lorsque indice == len(tableau), on obtient 
   le même effet qu'avec tableau.append(valeur).

   Cette fonction ne modifie pas le tableau passé en paramètre, mais renvoie 
   au contraire une copie de celui-ci à laquelle a été rajoutée la valeur à 
   insérer.
   """

   N = len(tableau)

   if 0 <= indice <= N:
      # Étape 1:
      # On crée une copie en réservant la place supplémentaire nécessaire:
      copie = [None]*(N+1)

      # Étape 2: 
      # On recopie toutes les valeurs juqu'à la position d'insertion

      for i in range(indice):
         copie[i] = tableau[i]

      # Étape 3:
      # On insère la nouvelle valeur
      copie[indice] = valeur

      # Étape 4: 
      # On recopie les valeurs restantes, décallées d'une position
      for i in range(indice, N):
         copie[i + 1] = tableau[i]

      return copie
   else:
      raise IndexError("Indice illégal")

Vous pouvez visualiser avec python tutor le déroulé exact de cet algorithme (les étapes correspondant aux commentaires du code ci-dessus saffichent dans la console pour faciliter la compréhension).

Insertion dans un tableau «en place»

À présent, nous aimerions non pas renvoyer une copie contenant la valeur à insérer, mais modifier directement le tableau passé en paramètre pour insérer la valeur.

Nous utiliserons un algorithme sensiblement différent pour obtenir le résultat recherché. Nous nous autoriserons lutilisation de append(), car il faut bien disposer dun moyen pour ajouter une valeur au tableau, sans pour autant tricher en utilisant directement insert.

def insertion(tableau, indice, valeur):
   """
   Insère la 'valeur' à la position donné par 'indice' dans le tableau. 
   On doit nécessairement avoir 0 <= indice <= len(tableau) sous peine
   de déclencher une erreur. Lorsque indice == len(tableau), on obtient 
   le même effet qu'avec tableau.append(valeur).

   Cette fonction modifie en place le tableau passé en paramètre, et ne
   renvoie donc aucune 
   """

   N = len(tableau)

   if 0 <= indice <= N:
      # Étape 1:
      # On rajoute la nouvelle valeur en bout de tableau
      tableau.append(valeur)

      # Étape 2: 
      # Tant que la nouvelle valeur n'est pas à la bonne position,
      # on l'échange avec sa voisine de gauche.

      pos = N # indice actuel de la nouvelle valeur
      while pos > indice:
         tableau[pos], tableau[pos - 1] = tableau[pos - 1], tableau[pos]
         pos -= 1
   else:
      raise IndexError("Indice illégal")

Le comportement de ce nouvel algorithme peut comme dhabitude être observé sur python tutor.

Coût de lalgorithme dinsertion.

En algorithmique, une notion très importante est celle de coût dun algorithme, qui correspond grosso-modo au nombre détapes nécessaires à son exécution. On parle aussi de complexité dun algorithme.

Quel est le coût dune insertion ?

  • Pour lalgorithme avec recopie, nous devons créer un nouveau tableau (une opération), puis recopier chaque valeur du tableau initial vers la copie (\(N\) opérations, où \(N\) est la taille du tableau initial), quelles soient placées avant où après la position dinsertion. Enfin, nous devons rajouter la valeur à insérer au bon endroit (une étape). Nous pouvons donc comptabiliser \(N + 2\) étapes. Lorsque la valeur de \(N\) est grande, la constante 2 est négligeable, nous dirons donc que le nombre détapes, cest-à-dire le coût de cet algorithme, est proportionnel à la taille des données \(N\).

    Définition: Un algorithme pour lequel le coût (la complexité) est proportionnel à la taille des données \(N\) est appelé un algorithme de complexité linéaire.

    Concrètement, dire que la complexité est linéaire signifie que si on double la taille des données, on double le temps dexécution. Si on triple la taille des données, on triple le temps dexécution, etc

  • Pour lalgorithme dinsertion en place, il y a une étape pour ajouter la valeur à insérer à la fin du tableau, mais ensuite le nombre détapes peut varier en fonction de la position dinsertion. Dans le pire des cas, on insère en position 0 et il faudra pratiquer \(N\) échanges de données. On se retrouve donc avec \(N + 1\) étapes, que lon peut approximer par \(N\). Le coût est là encore linéaire (dans le pire des cas).

    En informatique, on distingue parfois le coût moyen du coût dans le pire des cas. Pour certains algorithmes, il peut y avoir une différence. Dans le cas de linsertion en place, on peut montrer que le coût moyen est \(\frac{N}2\) (puisquen moyenne on insérera au milieu du tableau), ce qui reste proportionnel à \(N\). Le coût moyen est donc lui aussi linéaire, la constante \(\frac12\) ne change rien à laffaire.

Insertion dans un tableau ordonné

Supposons à présent que le tableau soit trié dans lordre croissant. On souhaite insérer une nouvelle valeur de façon à ce que le tableau reste trié: il ny a donc plus besoin de préciser la position dinsertion, elle sera déterminée automatiquement.

def insertion_ordonnée(tableau, valeur):
   """
   Insère valeur dans le 'tableau' supposé trié dans l'ordre croissant,
   en place, de façon à ce que le tableau final soit encore trié dans 
   l'ordre croissant.
   """

   # Étape 1: on rajoute la nouvelle valeur en bout de tableau
   tableau.append(valeur)

   # Étape 2:
   # Tant que la nouvelle valeur est inférieure à sa voisine de gauche,
   # on l'échange avec celle-ci (en faisant attention à bien s'arrêter
   # si on arrive au début du tableau)

   pos = len(tableau)
   while pos > 0 and tableau[pos-1] > tableau[pos]:
      tableau[pos], tableau[pos - 1] = tableau[pos - 1], tableau[pos]
      pos -= 1

On peut sassurer expérimentalement que cet algorithme fonctionne sur python tutor.

Preuve de la correction de cet algorithme

Cette section du cours est plus compliquée, et peut être omise en première lecture. Le notions abordées sont cependant explicitement au programme de NSI (dès la Première, mais aussi en Terminale), et ne doivent pas être ignorées.

Nous nous rendons bien compte expérimentalement que cet algorithme fonctionne. Mais si les mathématiques (dont linformatique est issue) nous ont appris quelque chose, cest quune preuve expérimentale nest pas une preuve !

Peut-on prouver que notre algorithme fonctionne ? La réponse est oui, et il faut démontrer deux choses:

  1. Sassurer que lalgorithme sarrête toujours, quelles que soient les données initiales, sans entrer dans une boucle infinie.
  2. Sassurer que, une fois terminé, lalgorithme a bien produit le bon résultat.

Le premier point est une preuve de terminaison de lalgorithme, le second une preuve de correction.

Voyons en détail ces deux preuves.

  1. Preuve de la terminaison: Il suffit de considérer lentier naturel pos. Celui-ci décroit strictement (dune unité, mais ce nest pas important ici) à chaque passage de la boucle while, tout en restant toujours positif (à cause de la condition pos > 0).

    Or, en mathématiques, une suite strictement décroissante dentiers positifs ou nuls ne peut pas être infinie. Cela nous garantit donc que lalgorithme ne peut boucler infiniment.

    On dit que pos est un variant pour la boucle.

    Définition: Un variant est une valeur entière positive ou nulle qui décroit strictement à chaque étape de lalgorithme, et permet grâce au principe mathématique évoqué plus tôt de garantir la terminaison de lalgorithme.

  2. Preuve de la correction: Une fois la nouvelle valeur rajoutée en bout de tableau, à chaque passage de la boucle while on peut constater que le tableau est séparé en trois zones:

    • toutes les valeurs avant pos sont rangées dans lordre croissant;
    • la nouvelle valeur (rangée à lindice pos) est strictement plus grande que sa voisine de gauche;
    • les valeurs après pos sont toutes plus grandes que la nouvelle valeur, et rangées dans lordre croissant.

    Si on note \(t_1 \leqslant \cdots \leqslant t_N\) les valeurs initiales et \(V\) la nouvelle valeur et \(p\) lindice pos, alors à un moment donné on aura ainsi:

    \[ t_1 \leqslant \cdots \leqslant t_{p-1} > V \leqslant t_{p} \leqslant \cdots t_N\]

    Après léchange de \(V\) avec sa voisine de gauche, on arrivera à:

    \[ t_1 \leqslant \cdots \leqslant t_{p-2} \longleftrightarrow V \leqslant t_{p - 1} \leqslant \cdots t_N\]

    Deux choses peuvent alors arriver: si \(t_{p-2} > V\), la boucle recommencera pour au moins un échange supplémentaire. Si au contraire \(t_{p-2} \leqslant V\), alors lalgorithme sarrête et le tableau final est trié.

    Nous avons utilisé ici ce que lon appelle un invariant, cest-à-dire une condition qui est vraie en début de boucle, et plus important reste vraie en fin de boucle.

    Définition: Un invariant de boucle est une condition qui est vraie en début et en fin de boucle. Elle permet de montrer quune certaine propriété reste valable tout au long de lexécution, et permet si elle est bien choisie de démontrer quune propriété donnée est vraie à lissue dune boucle, et donc de prouver la correction dun algorithme.

    Notons que trouver des variants ou des invariants pour un algorithme donné peut être très compliqué.

    À retenir:

    • Un variant est une suite strictement décroissante d’entiers naturels associé à chaque étape de l’algorithme. Celle-ci ne pouvant pas être mathématiquement infinie, elle garantit la terminaison de l’algorithme, c’est-à-dire que celui-ci ne pourra pas boucler infiniment.
    • Un invariant de boucle est une condition qui est toujours vérifiée au début et à la fin dune étape dune boucle, et permet de démontrer (s’il est bien choisi) que l’algorithme donne toujours la bonne réponse, ce que lon appelle la correction de lalgorithme.

Lalgorithme de tri par insertion

Une première version utilisant linsertion dans un tableau trié

Lalgorithme étudié précédemment nous donne un moyen simple de trier un tableau de données: cest exactement ce qui a été mis en évidence sur le dernier lien python tutor un peu plus haut: en insérant plusieurs valeurs dans un tableau déjà trié, on finit par avoir un tableau qui contient toutes les valeurs et reste trié.

Exploitons cette idée plus avant: dans un premier temps, on va créer une copie triée du tableau initial de la manière suivante:

  • On commence par une copie vide (un tableau de longueur 0)
  • On rajoute une à une les valeurs du tableau initial en utilisant lalgorithme dinsertion dans un tableau trié: celui-ci nous garantit quaprès chaque insertion, la copie sera triée dans lordre croissante, autorisant par la même linsertion de lélément suivant.
  • Lorsque lon a inséré toutes les valeurs, on a bien obtenu une copie du tableau initial (chaque valeur du tableau initial a été insérée dans la copie), et lalgorithme dinsertion nous garantit que la copie est triée.

On appelle cet algorithme un tri par insertion

def tri_insertion(tableau):
   copie = [] # Un tableau vide EST trié
   for valeur in tableau:
      insertion_ordonnée(copie, valeur)

   return copie

Difficile de faire plus simple (tous les détails un peu techniques ont en fait été étudiées dans la fonction insertion_ordonnée).

Assurons nous que cet algorithme fonctionne:

  • Expérimentalement avec python tutor;
  • Mathématiquement, en prouvant encore une fois la terminaison et la correction:
    • La terminaison est quasiment évidente, dans la mesure où lon utilise une boucle for dont le nombre détapes est connu initialement (cest la taille du tableau). On utilise aussi implicitement le fait que linsertion ordonnée se termine;
    • La correction a déjà été décrite plus haut: à chaque étape, on rajoute une valeur dans le tableau copie, et celui-ci est à la fois trié au début et à la fin de la boucle: cest linvariant recherché. Il démontre quà la fin de lexécution de la boucle, le tableau final est bien trié. Là encore, la correction de linsertion ordonnée implique celle du tri par insertion.

Une nouvelle version combinant le tri et linsertion ordonnée

Lalgorithme présenté précédemment a lavantage dêtre facile à mémoriser, car il est très court puisque lessentiel du travail est effectué dans une fonction auxilliaire (insertion_ordonnée).

Il est cependant possible de combiner ces deux algorithmes pour nen avoir quun seul: il sera un peu plus compliqué à comprendre initialement, mais aura lavantage dêtre bien plus court.

Pour comprendre (et découvrir) cet algorithme, commençons par nous intéresser à linvariant qui permettra den prouver la correction:

On fait varier \(i\) de 0 à \(N-1\), où \(N\) est la taille du tableau. On souhaite quen début et en fin de boucle, le tableau soit organisé de la manière suivante:

\[ \underbrace{t_0 \leqslant t_1\leqslant \cdots \leqslant t_{i-1}}_{\text{valeurs triées}} \;;\; \underbrace{t_i\;;\; t_{i+1} \;;\; \cdots \;;\; t_{N-1}}_{\text{valeurs non triées}}\]

Cest évidemment le cas au début, puisquavec \(i = 0\), la zone triée est vide. On sassure quau rang suivant cet invariant reste bien valide de la manière suivante: on va insérer la première valeur non triée \(t_i\) dans la partie de gauche en utilisant lalgorithme dinsertion ordonnée (en léchangeant avec ses voisines de gauche tant que lordre nest pas dans le bon sens). On aura alors inséré \(t_i\) quelque part dans la partie de gauche, et, quitte à réordonner les valeurs, le tableau sera dans la situation suivante:

\[ \underbrace{t'_0 \leqslant t'_1\leqslant \cdots \leqslant t'_{i-1} \leqslant t'_i}_{\text{valeurs triées}} \;;\; \underbrace{t_{i + 1}\;;\; t_{i+2} \;;\; \cdots \;;\; t_{N-1}}_{\text{valeurs non triées}}\]

On ne sait pas exactement où \(t_i\) a été inséré, cest pour cela que les valeurs triées sont notées avec des primes dans cette condition en fin de boucle.

La condition étant conservée entre le début et la fin de la boucle, on a donc bien un invariant.

Lorsque la boucle extérieure est terminée, on sera dans la situation suivante (garantie par notre invariant):

\[ \underbrace{t_0 \leqslant t'_1\leqslant \cdots \leqslant t'_{N-1} \leqslant t'_N}_{\text{valeurs triées}}\]

Cela montre bien la correction de lalgorithme. Pour la terminaison, il suffit de reprendre les arguments déjà évoqués pour la précédente version de lalgorithme.

Limplémentation en python découle directement de cette description:


def tri_insertion(t):
   """
   Trie le tableau 't' en place, dans l'ordre croissant. Ne
   renvoie aucune valeur significative.
   """
   for i in range(1, len(t)):
      j = i
      while j > 0 and t[j-1] > t[j]:
         t[j], t[j-1] = t[j-1], t[j]
         j -= 1

Cette algorithme est une version très condensée des fonctions tri_insertion et insertion_ordonnée précédentes.

Remarquons que la boucle de \(i\) démarre à la valeur 1, car une valeur isolée est déjà en elle-même un tableau trié (et en outre, la condition \(j > 0\) ne serait jamais vérifiée avec \(i = 0\)).

Encore une fois, examinons le fonctionnement de cet algorithme sur le site python tutor

Lalgorithme de tri par sélection

Nous allons directement donner lalgorithme de tri par sélection dans sa version condensée. Pour le découvrir, nous allons utiliser un invariant légèrement différent de celui utilisé pour le tri par insertion.

Nous allons là encore boucler sur la variable \(i\) entre \(0\) et \(N-1\), où \(N\) est la taille du tableau.

En début de boucle, le tableau vérifiera la structure suivante:

\[ \underbrace{t_0 \leqslant t_1\leqslant \cdots \leqslant t_{i-1}}_{\text{valeurs triées}} \;;\; \underbrace{t_i\;;\; t_{i+1} \;;\; \cdots \;;\; t_{N-1}}_{\begin{matrix}\text{valeurs non triées toutes}\hfill \\ \text{plus grandes que les}\hfill \\ \text{valeurs déjà triées}\hfill\end{matrix}}\]

Il suffit ensuite de chercher la valeur minimale parmi les valeurs non triées: celle-ci est plus grande (ou égale) à toutes les valeurs déjà triées: on la place alors à droite des valeurs déjà triées, conservant ainsi lordre croissant. On se retrouve alors dans la situation suivante:

\[ \underbrace{t_0 \leqslant t_1\leqslant \cdots \leqslant t_{i-~} \leqslant t_i}_{\text{valeurs triées}} \;;\; \underbrace{t'_{i+1}\;;\; t_{i+2} \;;\; \cdots \;;\; t_{N-1}}_{\begin{matrix}\text{valeurs non triées toutes}\hfill \\ \text{plus grandes que les}\hfill \\ \text{valeurs déjà triées}\hfill\end{matrix}}\]

On a donc bien découvert un invariant de boucle, qui nous garantira en outre quà la fin de lexécution de la boucle extérieure (sur \(i\)), on sera encore une fois dans la situation:

\[ \underbrace{t_0 \leqslant t'_1\leqslant \cdots \leqslant t'_{N-1} \leqslant t'_N}_{\text{valeurs triées}}\]

Prouvant ainsi la correction de notre algorithme. La terminaison ne pose aucun problème: la variable \(i\) varie dans une boucle for à \(N\) étapes, et la recherche du minimum utilisera au maximum le nombre déléments non trié encore présents: cela garantit que le programme sarrêtera.

Voici une implémentation:

def tri_sélection(t):
   """
   Trie en place le tableau 't', dans l'ordre croissant. 
   Ne renvoie aucune valeur significative.
   """

   for i in range(0, len(t)):
      # On recherche la valeur minimale à partir de l'indice i
      mini = t[i]
      jmini = i
      for j in range(i, len(t)):
         if t[j] < mini:
            mini = t[j]
            jmini = j
      # Et on l'échange avec la i-ième valeur:
      t[i], t[jmini] = t[jmini], t[i]

Observons le fonctionnement de cet algorithme sur python tutor.

Il est possible de raccourcir lécriture de cet algorithme sans en changer lessence: plutôt que de garder une variable mini contenant la plus petite valeur vue jusquà présent et jmini pour en stocker lindice, on peut directement échanger la valeur minimale avec la valeur dindice i: comme cela, on sait que la valeur la plus petite vue jusquà présent sera toujours à lindice i. Cela donne alors:

def tri_sélection(t):
   """
   Trie en place le tableau 't', dans l'ordre croissant. 
   Ne renvoie aucune valeur significative.
   """

   for i in range(0, len(t)):
      # On recherche la valeur minimale à partir de l'indice i
      for j in range(i + 1, len(t)):
         if t[j] < t[i]:
            t[i], t[j] = t[j], t[i]

Et une fois nest pas coutume voici son exécution.

Complexité des deux algorithmes de tri

Pour le tri par sélection

Commençons par étudier la complexité de lalgorithme de tri par sélection tel que dans sa dernière présentation: on a deux boucles imbriquées, une sur \(i\) allant de 0 à \(N-1\) (soit \(N\) étapes), et lautre sur \(j\) allant de \(i + 1\) à \(N-1\) (soit \(N-i - 1\) étapes).

Le nombre total détapes sera alors:

\[ (N - 0 - 1) + (N - 1 - 1) + (N - 2 - 1) + \cdots + (N - (N-1) - 1)\]

ce qui peut se simplifier en

\[ (N - 1) + (N-2) + \cdots + 2 + 1 + 0\]

On peut démontrer en mathématiques (cest au programme de la spécialité en classe de Première, lorsque lon étudie les suites arithmétiques) que cette somme vaut toujours:

\[ (N - 1) + (N-2) + \cdots + 2 + 1 + 0 = \frac{N(N-1)}2 = \frac12N^2 - \frac12N\]

Le terme important est le terme \(N^2\), lautre terme étant négligeable lorsque \(N\) est grnad: cela montre que le nombre détapes de lalgorithme de tri par sélection est proportionnel à \(N^2\): on dit alors que lalgorithme de tri par sélection est quadratique (ce mot signifie «qui se rapporte au carré»).

Grosso-modo, sur un tableau de taille 1000, il faudra environ 500000 étapes de calcul, ce qui est absolument énorme. Pour un tableau 10 fois plus grand, le nombre détapes sera multiplié par \(10^2 = 100\), ce qui nous amène environ à 50 millions détapes de calcul !

Dire quun algorithme a une complexité quadratique signifie concrètement que doubler la taille des données revient à multiplier le temps dexécution par \(2^2 = 4\), tripler la taille des données revient à multiplier le temps dexécution par \(3^2 = 9\), etc

Par rapport à un algorithme linéaire, le temps dexécution augmente de manière dramatique lorsque \(N\) devient grand.

Nous verrons dans la pratique que trier de gros tableaux (avec \(N\) de lordre de quelques dizaines de milliers) peut prendre plusieurs dizaines de secondes avec une implémentation naïve en python.

Il existe des algorithmes largement plus efficaces (pas linéaires, mais bien meilleurs que quadratiques), mais nous les étudierons en Terminale.

Pour le tri par insertion

Lévaluation de la complexité est un peu plus complexe, puisque linsertion ordonnée peut sinterrompre plus ou moins tôt. Mais examinons ce qui se passe dans le pire des cas (cest-à-dire lorsque la valeur à insérer doit toujours migrer au début du tableau, ce qui arrive lorsque le tableau est initialement trié dans lordre décroissant):

On a une boucle externe sur \(i\) allant de \(1\) à \(N-1\), et une boucle interne qui, dans le pire des cas, effectuera \(i\) échanges. Le nombre total déchanges sera alors:

\[ 1 + 2 + \cdots + (N-2) + (N-1) = \frac{N(N-1)}2\]

La complexité dans le pire des cas est donc exactement la même que pour le tri par sélection: il sagit là encore dun algorithme à la complexité quadratique.

Un peu de détente pour terminer

  • Une visualisation du tri par insertion:
  • La même chose pour le tri par sélection:
  • Lexcellent site visualgo comporte une section avec de nombreux algorithmes de tri. Les tri par sélection et insertion sont symbolisés par SEL et INS dans le menu. Vous pouvez aussi examiner dautres algorithmes de tri (dont le tri par fusion, appellé MERge sort en anglais).