Photo by Ariadne Barroso, CC0 Public Domain

Publié le : 01/09/2004

Par : Marion Videau & David Eck

Niveau intermédiaire

Niveau 2 : Intermédiaire

Les algorithmes de tri

Algorithmes

Histoire du numérique

Fondements

Selon le dictionnaire, « trier » signifie « répartir en plusieurs classes selon certains critères ». De manière plus restrictive, le terme de « tri » en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné. Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier.

Il est intéressant de constater qu’intuitivement, s’il lui est donné un ensemble à trier, tout un chacun met en place des stratégies de tri différentes selon le nombre d’éléments de l’ensemble, par exemple un jeu de 52 cartes ou 200 élèves à classer dans l’ordre alphabétique. Tri par sélection, tri par propagation, tri par insertion, tri rapide, tri par fusion… ces différentes méthodes ont chacune leurs particularités… et leur niveau de performance, qui correspond à la complexité de l’algorithme. La méthode la plus utilisée actuellement est sans doute la méthode de tri rapide ou Quicksort, qui a été inventée par Sir Charles Antony Richard Hoare en 1960 – d’aucuns disent que c’est l’algorithme le plus utilisé au monde !

Animation HTML5/JS réalisée par Nathan Gaberel, d’après l’applet Java réalisée par David Eck, adaptée en français par Tahia Benhaj-Abdellatif. Accéder aux sources.

Face à un exemple de taille faible, il peut sembler quelque peu dérisoire de pousser le raffinement jusqu’à trouver un algorithme de tri supplémentaire à appliquer sur un petit nombre d’éléments, car la différence de complexité y sera peu visible ; cependant, il faut garder en mémoire qu’on peut vouloir trier des centaines de milliers d’éléments et que si une différence de stratégie est visible sur de petits nombres tels que 52 ou 200, a fortiori sur de grands ensembles la différence de complexité sera d’autant plus sensible.

On peut illustrer le cas général en prenant l’exemple du tri d’entiers. C’est ce que présente l’animation ci-dessus. Les différentes méthodes sont tout d’abord montrées, sous forme de Tri visuel, appliquées au tri de 16 éléments. Un deuxième niveau, appelé Tri temporel, permet de tester les différents algorithmes en choisissant un grand nombre d’éléments. Enfin, le menu Log garde la trace des essais successifs, afin de pouvoir les comparer.

Pour en savoir plus sur les différentes méthodes de tri

Pour décrire plus précisément les différentes méthodes de tri, leur procédure, leur complexité, on suppose qu’on dispose d’un tableau tab de N entiers numérotés de 1 à N et qu’on cherche à trier les entiers dans l’ordre croissant, « de gauche à droite » si on veut donner une représentation du tableau. On écrira les procédures de tri avec un « pseudo-code français » qui devrait être suffisamment clair pour ne pas nécessiter de traduction des mots clés. Mais ce « pseudo-code » est aussi suffisamment proche d’un langage informatique pour qu’un informaticien puisse aisément le transcrire dans un langage de programmation existant comme Java ou C.

Décrire la façon dont les algorithmes sont implémentés dans un ordinateur n’est pas si difficile, car les langages se basent sur des constructions simples et standard. D’un langage à l’autre, ces instructions de base se retrouvent.

Variables
Les calculs sont stockés dans des variables ou dans des tableaux de variables. Pour des nombres entiers, on écrira entier n ; pour décrire un entier de nom « n » ou entier[] tab pour décrire un tableau de nom « tab » dont les éléments sont numérotés à partir de 1 : tab[1], tab[2]...

Affectation
Le symbole <- représente l’affectation de la valeur de la variable à droite du symbole à la variable à gauche du symbole.

Procédures ou « fonctions »
Les portions de codes réutilisables sont regroupées dans une procédure.
Par exemple :

procedure nom_de_procedure (entier n, entier[] tab)
  tab[n]

est une procédure de nom « nom_de_procedure » dont les paramètres sont l’entier « n » et le tableau « tab » et qui ajoute 1 au n^e élément du tableau. Cette procédure peut être réutilisée pour n’importe quel entier n et n’importe quel tableau tab, par exemple en écrivant nom_de_procedure (3, vecteur); on ajoutera 1 au 3^e élément du tableau vecteur. Cet exemple simpliste n’est pas très utile ! Mais dès que la procédure fait plusieurs dizaines de lignes, l’économie est conséquente.
Une fonction est une procédure qui retourne une valeur, par exemple :

procedure nom_de_procedure (entier n, entier[] tab)
  retourner tab[n] +1;
fin procedure

retourne la n^e valeur du tableau plus 1.

Procédures récursives
Les procédures peuvent appeler d’autres procédures définissant ainsi une hiérarchie de portions de code de manière concise et intégrée. Mais peut-on définir une procédure qui… s’appelle elle-même ? C’est possible, et même parfois très utile… à condition que l’on ne définisse pas une boucle sans fin.
Par exemple, dans un système où chaque individu est repéré par un numéro et où un tableau « mere » mémorise le numéro de la mère de quelqu’un, ou -1 s’il n’a pas de mère, on définit la procédure « biblique » suivante :

procedure qui_est_eve(entier quelqu_un, entier[] mere)
  si (mere[quelqu_un] = -1)
    alors retourner quelqu_un
  sinon retourner qui_est_eve(mere[quelqu_un], mere);
  fin si
fin procedure

Cette procédure va récursivement s’appeler elle-même tant qu’elle n’aura pas trouvé quelqu’un qui n’a pas de mère, Ève en l’occurrence. Cette procédure marchera bien si le tableau « mere » contient des valeurs cohérentes avec cette idée, mais sinon, elle pourra boucler sans fin.

Instruction conditionnelle
Selon la valeur d’un paramètre, on peut souhaiter exécuter une portion de code ou une autre. Les langages proposent des instructions conditionnelles pour cela. Par exemple :

si (valeur > seuil) alors faire_quelque_chose(valeur);
sinon faire_autre_chose();
fin si

teste si la valeur dépasse un seuil et exécute une procédure dans ce cas. La partie « sinon » est facultative.

Boucle de calcul
Un algorithme comporte des instructions à répéter un certain nombre de fois. Les langages proposent des boucles pour spécifier une telle répétition d’instruction. Par exemple :

pour(i de 1 à taille_du_tableau en incrémentant de 1)
  tab[i]

va ajouter 1 à tous les éléments d’un tableau.

Complexité des algorithmes

Afin d’évaluer la complexité des différents algorithmes de tri présentés, on comptera le nombre de comparaisons et d’échanges de valeur entre deux éléments du tableau sans prendre en compte les affectations et comparaisons sur des variables de comptage de boucles.

Les méthodes présentées sont de deux types :

des méthodes qui trient les éléments deux à deux, de manière plus ou moins efficace, mais qui nécessitent toujours de comparer chacun des N éléments avec chacun des N-1 autres éléments, donc le nombre de comparaisons sera de l’ordre de N² — on note cet ordre de grandeur \(\mathcal{O}(N^2)\). Par exemple, pour N=1000, N²=10⁶, pour N=10⁶, N²=10¹². Les algorithmes de ce type sont :
- une méthode de tri élémentaire, le tri par sélection ;
- et sa variante, le tri par propagation ou tri bulle ;
- une méthode qui s’apparente à celle utilisée pour trier ses cartes dans un jeu,
  le tri par insertion ;
des méthodes qui sont plus rapides, car elles trient des sous-ensembles de ces N éléments puis regroupent les éléments triés, elles illustrent le principe « diviser pour régner ». Le nombre de comparaisons est alors de l’ordre de N (log(N)). Par exemple, pour N=1000, N(log(N))=10000 environ, pour N=10⁶, N(log(N))=20×10⁶ environ. Les algorithmes de ce type sont :
- le fameux tri rapide ou Quicksort ;
- et enfin, le tri par fusion.

Cette liste n’est évidemment pas exhaustive. Il existe des méthodes particulièrement adaptées à certains types de données spécifiques. Le tri par base (radix sort) en est un exemple.

« Pseudo-code » et calcul de la complexité des algorithmes

Il consiste à trouver dans le tableau le numéro de l’élément le plus petit, c’est-à-dire l’entier min tel que tab[k] >= tab[min] pour tout k. Une fois ce numéro trouvé, les éléments tab[1] et tab[min] sont échangés – cet échange nécessite une variable temporaire de type entier – puis la même procédure est appliquée sur la suite d’éléments tab[2], ..., tab[N].

/* Procédure de tri par sélection */

procedure triSelection(entier[] tab)
  entier i, k;
  entier min;
  entier tmp;
  pour (i de 1 à N-1 en incrémentant de 1) faire

    /* recherche du numero du minimum */

    min <- i;
    pour (k de i+1 à N en incrémentant de 1) faire
      si (tab[k] < tab[min]) alors
        min <- k;
      fin si
    fin pour

    /* echange des valeurs entre la case courante et le minimum */

    tmp <- tab[i];
    tab[i] <- tab[min];
    tab[min] <- tmp;
  fin pour
fin procedure

Il est facile de compter le nombre d’opérations. Quel que soit l’ordre du tableau initial, le nombre de comparaisons reste le même, ainsi que le nombre d’échanges. À chaque itération, on considère l’élément tab[i] et on le compare successivement à tab[i+1], ..., tab[N]. On fait donc N-i comparaisons.

Le nombre total de comparaisons est donc de :
\[\sum_{i=1}^{N-1} N-i=\frac {N(N-1)}{2}\]

et il y a (N-1) échanges.

En ce qui concerne sa complexité, on dit que le tri par sélection est en \(\mathcal{O}(N^2)\), à la fois dans le meilleur des cas, en moyenne et dans le pire des cas, c’est-à-dire que son temps d’exécution est de l’ordre du carré du nombre d’éléments à trier.

Le « tri bulle » est une variante du tri par sélection. Il consiste à parcourir le tableau tab en permutant toute paire d’éléments consécutifs (tab[k],tab[k+1]) non ordonnés – ce qui est un échange et nécessite donc encore une variable intermédiaire de type entier. Après le premier parcours, le plus grand élément se retrouve dans la dernière case du tableau, en tab[N], et il reste donc à appliquer la même procédure sur le tableau composé des éléments tab[1], ..., tab[N-1]. Le nom de ce tri provient du déplacement des « bulles » les plus grandes vers la droite.

/* Procédure de tri bulle */ 

procedure triBulle(entier[] tab)
  entier i, k;
  entier tmp;
  pour (i de N à 2 en décrémentant de 1) faire
    pour (k de 1 à i-1 en incrémentant de 1) faire
      si (tab[k] > tab[k+1]) alors
        tmp <- tab[k];
        tab[k] <- tab[k+1];
        tab[k+1] <- tmp;
      fin si
    fin pour
  fin pour
fin procedure

Le nombre de comparaisons dans la procédure de tri bulle est le même que pour le tri par sélection :

\[\sum_{i=2}^{N} i-1=\frac {N(N-1)}{2}.\]

Le nombre d’échanges quant à lui dépend de l’ordre des éléments dans le tableau :

dans le meilleur des cas, le tableau initial est trié et il n’y a pas d’échange à faire ;
en moyenne, on montre que le nombre d’échanges est de :
\[\frac {N(N-1)}{4};\]
dans le pire des cas, les entiers du tableau sont initialement donnés dans l’ordre décroissant. Dans ce cas, on effectue l’échange à chaque comparaison, c’est-à-dire que le nombre d’échanges est alors de :
\[\frac {N(N-1)}{2}.\]

Quoi qu’il en soit, la complexité du tri bulle reste en \(\mathcal{O}(N^2)\), c’est-à-dire du même ordre de grandeur que le carré du nombre d’éléments.

Cette méthode de tri est très différente de la méthode de tri par sélection et s’apparente à celle utilisée pour trier ses cartes dans un jeu : on prend une carte, tab[1], puis la deuxième, tab[2], que l’on place en fonction de la première, ensuite la troisième tab[3] que l’on insère à sa place en fonction des deux premières et ainsi de suite. Le principe général est donc de considérer que les (i-1) premières cartes, tab[1],..., tab[i-1] sont triées et de placer la i^e carte, tab[i], à sa place parmi les (i-1) déjà triées, et ce jusqu’à ce que i = N.

Pour placer tab[i], on utilise une variable intermédiaire tmp pour conserver sa valeur qu’on compare successivement à chaque élément tab[i-1], tab[i-2], ... qu’on déplace vers la droite tant que sa valeur est supérieure à celle de tmp. On affecte alors à l’emplacement dans le tableau laissé libre par ce décalage la valeur de tmp.

/* Procédure de tri par insertion */ 

procedure triInsertion(entier[] tab)
  entier i, k;
  entier tmp;
  entier k;
  pour (i de 2 à N en incrémentant de 1) faire
    tmp <- tab[i];
    k <- i; 
    tant que (k > 1 et tab[k - 1] > tmp) faire
      tab[k] <- tab[k - 1];
      k <- k - 1;
    fin tant que
  tab[k] <- tmp;
  fin pour
fin procedure

La comparaison avec les deux algorithmes précédents montre que la complexité du tri par insertion est plus fortement dépendante de l’ordre du tableau initial. Nous comptons ici le nombre de comparaisons (qui est le nombre de décalages à un près) :

dans le meilleur des cas, le tableau initial est trié et on effectue alors une comparaison à chaque insertion, on effectue donc N-1 comparaisons ;
en moyenne, on montre que le nombre de comparaisons est de :
\[N-1 + \frac {N(N-1)}{4};\]
dans le pire des cas, les entiers du tableau sont initialement donnés dans l’ordre décroissant. Dans ce cas, on effectue l’échange à chaque comparaison, c’est-à-dire que le nombre d’échanges est alors de :
\[\frac {N(N-1)}{2}.\]

Contrairement aux tris par sélection et bulle qui nécessitent un nombre constant de comparaisons, le tri par insertion ne conduit qu’à très peu de comparaisons lorsque le tableau initial est presque en ordre. Ce tri a donc de meilleures propriétés.

Cette méthode de tri, probablement la plus utilisée actuellement — d’aucuns disent même que c’est l’algorithme le plus utilisé au monde — a été inventée par Sir Charles Antony Richard Hoare en 1960. Elle illustre le principe dit « diviser pour régner », qui consiste à appliquer récursivement une méthode destinée à un problème de taille donnée à des sous-problèmes similaires, mais de taille inférieure. Ce principe général produit des algorithmes qui permettent souvent d’importantes réductions de complexité.

On considère un élément au hasard dans le tableau, le pivot, dont on affecte la valeur à une variable, disons pivot. On procède alors à une partition du tableau en 2 zones : les éléments inférieurs ou égaux à pivot et les éléments supérieurs ou égaux à pivot. Si on parvient à mettre les éléments plus petits en tête du tableau et les éléments plus grands en queue de tableau, alors on peut placer la valeur de pivot à sa place définitive, entre les deux zones. On répète ensuite récursivement la procédure sur chacune des partitions créées jusqu’à ce qu’elle soit réduite à un ensemble à un seul élément.

/* Procédure de tri rapide */

fonction partition(entier[] tab, entier debut, entier fin)
retourne un entier
  entier indicePivot;
  entier k <- debut;
  entier tmp;
  entier i;

  /* la valeur pivot est le premier élément du tableau */
  /* afin d'éviter les mauvaises répartitions pour ce tri */
  /* on tire aléatoirement la valeur du pivot avant de commencer */

  indicePivot <- entier aléatoire entre debut et fin;
  tmp <- tab[indicePivot];
  tab[indicePivot] <-  tab[debut];
  tab[debut] <- tmp;

  pour (i de debut+1 à fin en incrémentant de 1) faire
    si (tab[i] < tab[debut]) alors
      tmp <- tab[i];
      tab[i] <- tab[k+1];
      tab[k+1] <- tmp;
      k <- k + 1;
    fin si
  fin pour
  tmp <- tab[debut]
  tab[debut] <- tab[k];
  tab[k] <- tmp; retourner k; 
fin fonction 

procedure triRapideR(entier[] tab, entier debut, entier fin)
  si (fin > debut) alors
    entier indicePivot <-   partition(tab, debut, fin);
    triRapideR(tab, debut, indicePivot - 1);
    triRapideR(tab, indicePivot + 1, fin);
  fin si
fin procedure

procedure triRapide(entier[] tab)
  triRapideR(tab, 1, N);
fin procedure

La partie du tri la plus sensible reste le choix du pivot. Dans l’algorithme précédent, il est choisi au hasard parmi les éléments du tableau, mais ce choix peut se révéler catastrophique : si le pivot est à chaque choix le plus petit élément du tableau, alors le tri rapide dégénère en tri par sélection.

On montre que la complexité de ce tri est :

dans le meilleur des cas, en \(\mathcal{O}(N \log{}N)\);
en moyenne, en \(\mathcal{O}(N\log{}N)\) ;
dans le pire des cas, en \(\mathcal{O}(N^2)\).

Il existe bon nombre d’astuces pour rendre le cas dégénéré du tri rapide le plus improbable possible, ce qui rend finalement cette méthode la plus rapide en moyenne parmi toutes celles utilisées.

Ce tri est un autre exemple de méthode qui applique le principe « diviser pour régner ». En effet, étant données deux suites d’éléments triés, de longueurs respectives L1 et L2, il est très facile d’obtenir une troisième suite d’éléments triés de longueur L1 + L2, par « interclassement » (ou fusion) des deux précédentes suites, comme illustré dans la procédure fusion.

Pour les besoins de la procédure triFusion, nous allons donner la forme suivante à la procédure fusion qui interclasse deux suites d’éléments placés dans un tableau tab, respectivement entre les indices debut et mil et entre les indices mil + 1 et fin :

/* Procédure de fusion */ 

procedure fusion(entier[] tab, entier[] tmp, entier debut, entier mil, entier fin)
  entier k;
  entier i <- debut;
  entier j <- mil + 1; 
  pour (k de debut à fin en incrémentant de 1) faire 
    si ((j > fin) ou (i <= mil et tab[i] < tab[j])) alors
      tmp[k] <- tab[i];
      i <- i + 1;
    sinon
      tmp[k] <- tab[j];
      j <- j + 1;
    fin si
  fin pour
  pour (k de debut à fin en incrémentant de 1) faire
  tab[k] <- tmp[k];
  fin pour
fin procedure

On constate que la procédure de fusion nécessite un tableau intermédiaire aussi grand que le nombre d’éléments à interclasser. C’est là où réside le principal inconvénient du tri fusion, car si sa complexité dans tous les cas est en \(\mathcal{O}(N \log{}N)\), c’est au prix d’un tableau annexe aussi grand que le tableau initial, ce qui peut se révéler handicapant dans les situations où la place mémoire est restreinte.

La procédure récursive de tri fusion est alors :

/* Procédure récursive de tri fusion */

procedure triFusionR(entier[] tab, entier[] tmp, entier debut, entier fin)
  si (debut < fin) alors
    entier milieu <- (debut + fin)/2;
    triFusionR(tab, tmp, debut, milieu);
    triFusionR(tab, tmp, milieu + 1, fin);
    fusion(tab, tmp, debut, milieu, fin);
  fin si
fin procedure

procedure triFusion(entier[] tab)
  entier[] tmp <- tableau de taille N;
  triFusionR(tab, tmp, 1, N);
fin procedure

La version utilisée dans l’animation de démonstration est en fait la version itérative. Elle consiste à trier des sous-suites de longueur 2, 4, …, une puissance de 2, jusqu’à la longueur du tableau.

On obtient alors :

/* Procédure itérative de tri fusion */

procedure triFusionI(entier[] tab)
  entier[] tmp <- tableau de taille N;
  entier i <- 1;
  entier debut <- 1;
  entier fin <- debut + i + i - 1;
  tant que (i < N) faire
    debut <- 1;
    tant que (debut + i -1 < N) faire
      fin <- debut + i + i - 1; 
      si (fin > N) alors
        fin <- N;
      fusion(tab, tmp, debut,    debut + i - 1, fin);
      debut <- debut + i + i;
    fin tant que
    i <- i + i;
  fin tant que
fin procedure

Newsletter

Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité