Algorithmes de tri

10-02-2023

Objectifs

  • comprendre les relations d’ordre sur divers types et structures de données

  • connaître le fonctionnement de la méthode sort définie sur les listes

  • découvrir les algorithmes de tri élémentaires : par sélection et par insertion

  • s’initier à la complexité des algorithmes et comprendre l’intérêt d’une telle étude.

Motivation

Réaliser un tri ou un classement est une opération relativement courante dans la vie quotidienne :

  • classer les cartes d’un jeu,

  • classer par ordre alphabétique les livres d’une bibliothèque,

  • classer des concurrents selon leurs performances, etc…

Remarque

Dans la vie courante, les deux verbes trier et classer ne sont pas synonymes.

  • trier ou effectuer un tri c’est répartir les éléments en paquets correspondant à un certain critère : par exemple séparer les personnes d’une assemblée selon leur sexe ou selon leur langue maternelle.

  • classer ou effectuer un classement c’est mettre des éléments selon un certain ordre : par exemple ranger les personnes d’une assemblée de la plus petite à la plus grande, ou de la plus jeune à la plus vieille.

En informatique les mots tri et trier sont à prendre avec le sens de classement et classer.

Gérer un agenda téléphonique est aussi une forme de tri, puisqu’un ordre (alphabétique selon le nom des individus) est appliqué, même si ce tri est fait petit à petit, au fur et à mesure de l’insertion de nouveaux numéros.

Un tri porte généralement sur un nombre assez important de données. En effet, lorsque l’on a peu de numéros de téléphone à gérer, on se contente souvent de les inscrire dans l’ordre où ils sont connus sur une feuille libre, mais, dès que leur nombre devient trop important 1 , on ressent le besoin de les classer et donc de les trier dans un agenda, afin d’accéder plus rapidement à une information.

Effectuer un tri est souvent assez long et fastidieux (du moins quand les données initiales ne sont pas ou peu triées). Cependant, l’intérêt d’une telle opération, une fois réalisée, est de pouvoir facilement accéder aux différentes données en s’appuyant sur le critère du tri. C’est le cas en particulier de l’algorithme efficace de recherche dichotomique (cf Recherche dichotomique).

Un tri est toujours réalisé selon un critère, particulier et arbitraire, portant sur les données.

Ainsi, on peut arbitrairement choisir de classer les livres d’une bibliothèque selon un ordre

  • croissant ou décroissant par auteurs ou par titres ;

  • ou numérique selon les dates de parutions, le nombre de pages 2 …

Du fait de leur fréquente utilisation, les tris ont été très étudiés en informatique et font partie du savoir de base de tous les informaticiens. Ils constituent une excellente introduction à l’analyse des algorithmes et sont un très bon support pour l’étude de problèmes plus généraux. De nombreux algorithmes de tri existent, plus ou moins efficaces et plus ou moins faciles à mettre en œuvre. Nous nous limiterons à l’étude de deux d’entre eux 3 :

  • le tri par sélection

  • le tri par insertion.

Trier en Python

Méthode sort

Commençons par quelques mots sur une méthode prédéfinie en Python pour les listes : la méthode sort.

Observons une utilisation de cette méthode :

>>> l1 = [3, 1, 4, 1, 5, 9, 2]
>>> l1.sort()
>>> l1
[1, 1, 2, 3, 4, 5, 9]

On voit sur cet exemple que

  • l’application de la méthode sort sur la liste l ne renvoie aucune valeur (ou plus exactement renvoie None)

  • et qu’à l’issue de cette application, la liste l a été modifiée : ses éléments sont maintenant rangés dans l’ordre croissant : la liste est triée.

Il n’y a pas que les listes de nombres qu’il est possible de trier. On peut trier des listes de chaînes de caractères :

>>> l2 = list('TIMOLEON')
>>> l2.sort()
>>> l2
['E', 'I', 'L', 'M', 'N', 'O', 'O', 'T']
>>> l4 = list('Timoleon')
>>> l4.sort()
>>> l4
['T', 'e', 'i', 'l', 'm', 'n', 'o', 'o']
>>> l5 = ['La', 'cigale', 'et', 'la', 'fourmi']
>>> l5.sort()
>>> l5
['La', 'cigale', 'et', 'fourmi', 'la']

On peut aussi trier des listes de tuples :

>>> l6  = [(3, 'D'), (1, 'B'), (3,'A'), (4, 'C')]
>>> l6.sort()
>>> l6
[(1, 'B'), (3, 'A'), (3, 'D'), (4, 'C')

On peut aussi trier dans l’ordre inverse en ajoutant reverse=True en paramètre de la méthode :

>>> l1.sort(reverse=True)
>>> l1
[9, 5, 4, 3, 2, 1, 1]
>>> l2.sort(reverse=True)
>>> l2
['T', 'O', 'O', 'N', 'M', 'L', 'I', 'E']

Fonction sorted

À côté de la méthode sort réservée aux listes, existe une fonction applicable à n’importe quel itérable qui renvoie une nouvelle liste dont les éléments sont ceux de l’itérable dans l’ordre croissant. Cette fonction se nomme sorted.

>>> sorted('Timoleon')
['T', 'e', 'i', 'l', 'm', 'n', 'o', 'o']
>>> sorted(set('Timoleon'))
['T', 'e', 'i', 'l', 'm', 'n', 'o']

Cette fonction accepte aussi le paramètre optionnel reverse

>>> sorted('Timoleon', reverse=True)
['o', 'o', 'n', 'm', 'l', 'i', 'e', 'T']

La section suivante vise à essayer de comprendre ce que signifient ces classements obtenus avec la méthode sort ou la fonction sorted.

Comparer deux valeurs

Pour trier une structure de données, il faut en comparer les éléments. En mathématiques, les opérations de comparaisons sont désignées par les opérateurs usuels \(=\), \(\leq\), \(<\), etc …

Nous retrouvons ces opérateurs de comparaison dans tous les langages de programmations. En Python, nous avons les opérateurs prédéfinis ==, <=, <, etc …

La fonction sorted et la méthode sort utilisent l’ordre défini par l’opérateur <=.

Nous allons examiner dans cette partie la signification de cet opérateur qui est évidente pour certains types de données, mais peut-être moins pour d’autres. Et d’ailleurs que pouvons nous comparer avec ces opérateurs prédéfinis. Répondent-ils à tous nos besoins ?

Comparer une carotte à un navet ?

L’opérateur <= permet de comparer toutes sortes de types de données. Mais il n’est capable de comparer que des valeurs de même type.

Si on tente de comparer deux valeurs de types non comparables, une exception TypeError est déclenchée :

>>> [] <= (1, 2)
Traceback (most recent call last):
...
TypeError: unorderable types: list() <= tuple()

Les nombres

L’opérateur <= appliqué sur des données numériques, entiers ou flottants, correspond à l’ordre numérique bien connu.

Les entiers et les flottants sont comparables entre eux :

>>> 1 <= 3.5
True

Les booléens

Le booléen False est «plus petit» que le booléen True.

>>> False <= True
True
>>> True <= False
False

Remarque

Rares sont les occasions pour lesquelles on a besoin de trier des booléens.

Les caractères

L’ordre des caractères est déterminé par celui des numéros Unicode associés. Plus précisément un caractère \(c_1\) est «plus petit» qu’un caractère \(c_2\) si le numéro unicode du premier est plus petit que celui du second.

>>> ord('T')
84
>>> ord('a')
97
>>> 'T' <= 'a'
True

Les chaînes de caractères

Pour les chaînes de caractères, l’opérateur <= correspond à l’ordre lexicographique, qui est la généralisation de l’ordre alphabétique utilisé par exemple pour classer les mots dans un dictionnaire.

L’ordre lexicographique consiste à comparer les premiers caractères. En cas d’égalité des premiers caractères on passe aux deuxièmes. Etc …

>>> 'Timoleon' <= 'calbuth'
True

La chaîne vide est inférieure à toutes les autres chaînes de caractères.

Les tuples, les listes

Les tuples et les listes sont elles aussi comparables. L’ordre défini par l’opérateur <= est aussi l’ordre lexicographique. Bien entendu, il est nécessaire que les éléments de mêmes rangs soient comparables.

>>> ('A', 1) <= ('A', 2)
True
>>> ('A', 1, 3) <= ('A', 1)
False

Le tuple vide est inférieur à tous les autres tuples. De même pour la liste vide.

Quid des dictionnaires ?

Les dictionnaires ne sont pas comparables à l’aide de l’opérateur <=. Il serait d’ailleurs a priori bien difficile d’en donner une signification générale.

>>> dict() <= dict()
Traceback (most recent call last):
...
TypeError: unorderable types: dict() <= dict()

Si nous voulons classer une liste de valeurs de types dictionnaires, il est donc nécessaire de définir nos propres fonctions de comparaison.

Définir ses propres fonctions de comparaisons

Nous venons de le voir, il est parfois nécessaire au programmeur de définir ses propres fonctions de comparaison. C’est le cas s’il veut comparer deux valeurs construites à l’aide de dictionnaires. C’est le cas aussi dans d’autres circonstances.

Considérons l’exemple d’une petite classe de quatre étudiants chacun ayant une note d’informatique, ces données étant représentées par une liste de couples (nom, note)

>>> classe = [('Timoleon', 13), ('Calbuth', 15), ('Talon', 12), ('Cru', 11)]

On peut vouloir trier cette liste d’étudiants par ordre alphabétique. La méthode sort convient parfaitement pour cela, puisque l’ordre des couples se fera en comparant d’abord les noms, et en cas d’égalité les notes.

>>> sorted(classe)
[('Calbuth', 15), ('Cru', 11), ('Talon', 12), ('Timoleon', 13)]

Mais comment faire pour trier cette liste selon l’ordre de mérite ? On peut bien entendu, construire une nouvelle liste contenant les couples (note, nom), et utiliser la méthode sort.

Une autre idée consiste à définir une fonction qui prend deux couples (nom, note) et les compare selon la note d’abord.

Fonctions compare

Les fonctions de comparaison que nous concevrons et que nous nommerons compare auront donc toutes deux paramètres x et y, les deux valeurs à comparer, et renverront l’un des trois nombres -1, 0 ou 1 selon la spécification suivante :

  • -1 si x est plus petit que y ;

  • 0 si x est égal à y ;

  • 1 si x est plus grand que y.

Voici l’exemple d’une telle fonction de comparaison qui permet de comparer deux séquences par leur deuxième élément :

def seq_compare_deuxieme(x, y):
    """
    :param x, y: (sequentielle de longueur >= 2) deux données de mêmes types
    :return: (int) 
      - -1 si x < y
      - 0 si x == y
      - 1 si x > y
    :CU: x et y doivent être d'un type pour lequel les opérateurs de comparaison <, <=, == 
         peuvent s'appliquer
    :Exemples:

    >>> seq_compare_deuxieme((1,2), (3,4))
    -1
    >>> seq_compare_deuxieme((3, 2), (4, 1)
    1
    >>> seq_compare_deuxieme((3, 3),(3, 3))
    0
    """
    if x[1] < y[1]:
        res = -1
    elif x[1] > y[1]:
        res = 1
    else:
        res = 0
    return res

Avec cette fonction seq_compare_deuxieme, et la fonction cmp_to_key prédéfinie dans le module functools, il nous est possible de trier la liste par ordre de mérite, dans l’ordre croissant :

>>> import functools
>>> sorted(classe, key=functools.cmp_to_key(seq_compare_deuxieme))
[('Cru', 11), ('Talon', 12), ('Timoleon', 13), ('Calbuth', 15)]

ou dans l’ordre décroissant :

>>> sorted(classe, key=cmp_to_key(seq_compare_deuxieme), reverse=True)
[('Calbuth', 15), ('Timoleon', 13), ('Talon', 12), ('Cru', 11)]

Remarque

On peut aussi se dispenser d’invoquer la fonction cmp_to_key en donnant au paramètre key une fonction donnant la clé selon laquelle on veut trier. Par exemple, si on veut trier une liste de couples selon la seconde composante, alors il suffit de donner une fonction donnant accès à la seconde composante d’un couple. En voici un exemple

>>> def second(x):
        return x[1]
>>> sorted(classe, key=second)
[('Cru', 11), ('Talon', 12), ('Timoleon', 13), ('Calbuth', 15)]

Mieux encore, il n’est pas forcément nécessaire de définir préalablement la fonction second. On peut utiliser une définition de fonction anonyme en utilisant le mot-clé lambda

>>> sorted(classe, key=lambda x: x[1])
[('Cru', 11), ('Talon', 12), ('Timoleon', 13), ('Calbuth', 15)]

Spécification du problème du tri

Dans ce cours, nous nous contenterons de trier les éléments d’une liste. Tout ce qui sera dit pourra être transposé sans difficulté à d’autres structures de données séquentielles 4 .

Nous supposerons

  • que ces listes à trier sont homogènes, c’est-à-dire que leurs éléments sont tous d’un même type 5, par exemple des listes de nombres, ou de chaînes de caractères …

  • et que les éléments de cette liste peuvent être ordonnés selon un ordre que l’on notera \(\leq\).

Trier une liste c’est obtenir, à partir d’une liste \(\ell\), une liste contenant les mêmes éléments mais rangés par ordre croissant.

Du point de vue du traitement des données, cette définition n’est pas suffisante :

  • doit-on construire une nouvelle liste et laisser la liste \(\ell\) inchangée ? (comme la fonction sorted)

  • ou bien doit-on transformer la liste de sorte qu’elle soit triée ? (comme la méthode sort)

Dans ce cours nous traiterons le second problème. Le premier problème peut aisément être traité en adaptant les algorithmes proposés.

Voici donc la spécification du problème de tri que nous nous fixons :

Construction d’une liste triée

Entrée : \(\ell\) une liste de longueur \(n\), homogène, d’éléments ordonnables.

Sortie : Aucune

Effet de bord : la liste \(\ell\) est triée.

Nous ne répèterons plus cette spécification du problème dans les algorithmes qui suivront.

Tri par sélection

Sélection du minimum

Commençons par un algorithme permettant de rechercher l’indice d’un élément de valeur minimale dans une tranche de liste.

L’algorithme

Sélection du minimum dans une tranche de liste

Entrée : \(\ell\) une liste de longueur \(n\), homogène, d’éléments ordonnables, et \(a\) et \(b\) deux indices, \(0\leq a < b\leq n\)

Sortie : indice d’un élément minimal de la tranche \(\ell[a:b]\).

  1. \(ind_{min}\leftarrow a\)

  2. Pour \(i\) variant de \(a+1\) à \(b-1\)

  3. \(\quad\) Si \(\ell[i]<\ell[ind_{min}]\)

  4. \(\quad\quad ind_{min}\leftarrow i\)

  5. \(\quad\) Fin Si

  6. Fin Pour

  7. Renvoyer \(ind_{min}\)

Son coût

Notons \(\mathrm{c}_{\mathrm{select}}(k)\) le nombre de comparaisons d’éléments de la liste pour trouver le plus petit dans une tranche de longueur \(k = b-a\).

À chaque étape de la boucle pour, on effectue une comparaison (ligne 3 de l’algorithme). Le nombre de comparaisons est donc égal au nombre d’itérations de cette boucle. Autrement dit

\[\mathrm{c}_{\mathrm{select}}(k) = \sum_{i=a+1}^{b-1} 1 = (b-1) - (a+1) + 1 = b-a-1 = k - 1.\]

Algorithme du tri par sélection

L’algorithme

Tri d’une liste

  1. Pour \(i\) variant de \(0\) à \(n-2\)

  2. \(\quad ind_{min}\leftarrow \mathtt{select\_min(\ell,i,n)}\)

  3. \(\quad \mathtt{echanger}\ \ell[i]\mbox{ et }\ell[ind_{min}]\)

  4. Fin Pour

Un exemple

Le tableau Un tri par sélection montre l’évolution de la tranche triée lors du tri par sélection de la liste des lettres du mot TIMOLEON.

Un tri par sélection

\(i\)

\(ind_{min}\)

\(\ell\)

0

5

E IMOLTON

1

1

EI MOLTON

2

4

EIL OMTON

3

4

EILM OTON

4

7

EILMN TOO

5

6

EILMNO TO

6

7

EILMNOOT

Son coût

Notons \(\mathrm{c}_{\mathrm{tri-select}}(n)\) le nombre de comparaisons d’éléments d’une liste de longueur \(n\) lors du tri par sélection de cette liste.

L’algorthme du tri par sélection se limitant à une seule boucle pour, le nombre de comparaisons est égal à la somme des nombres de comparaisons effectuées à chaque itération lors de la sélection du minimum.

À l’étape numéro \(i\) de cette boucle, on sélectionne le minimum dans une tranche de liste de longueur \(n - i\). On a donc

\[\mathrm{c}_{\mathrm{tri-select}}(n) = \sum_{i=0}^{n-2} \mathrm{c}_{\mathrm{select}}(n-i).\]

Compte-tenu du coût de la sélection établie plus haut, on obtient :

\[\begin{split}\mathrm{c}_{\mathrm{tri-select}}(n) &= \sum_{i=0}^{n-2} (n-i-1)\\ &= \frac{n(n-1)}{2}\\ &\sim \frac{n^2}{2}.\end{split}\]

Le nombre de comparaisons croît donc quadratiquement (degré 2) avec la longueur de la liste à trier.

Autrement dit, lorsqu’on multiplie la longueur de la liste d’un facteur \(c\), le nombre de comparaisons est multiplié par \(c^2\).

Tri par insertion

Insertion dans une tranche de liste triée

L’algorithme

Insertion dans une tranche de liste triée

Entrée : \(\ell\) une liste de longueur \(n\), homogène, d’éléments ordonnables, et \(i<n\) un indice, tel que \(\ell[0:i]\) est trié

Sortie : aucune

Effet de bord la tranche \(\ell[0:i+1]\) est triée.

  1. \(aux \leftarrow \ell[i]\)

  2. \(k \leftarrow i\)

  3. TQ \(k\geq 1\) et \(aux < \ell[k-1]\)

  4. \(\quad\ell[k]\leftarrow\ell[k-1]\)

  5. \(\quad k\leftarrow k-1\)

  6. Fin TQ

  7. \(\ell[k]\leftarrow aux\)

Son coût

Notons \(\mathrm{c}_{\mathrm{insert}}(i)\) le nombre de comparaisons d’éléments de la liste pour insérer l’élément d’indice \(i\) dans la tranche \(\ell[0:i+1]\).

Ce nombre de comparaisons ne dépend pas uniquement de l’indice \(i\) mais aussi du contenu de la liste.

  • Dans le meilleur des cas, une seule comparaison suffit. Cela arrive lorsque l’élément d’indice \(i\) est supérieur ou égal à celui qui le précède, et donc est déjà à sa place dans la liste.

  • Dans le pire des cas, il faut comparer cet élément à chacun de ceux qui le précède, ce qui arrive lorsqu’il est plus petit que chacun d’eux. Et dans ce cas on effectue \(i\) comparaisons.

Ainsi on a

\[1\leq \mathrm{c}_{\mathrm{insert}}(i) \leq i.\]

Le tri

L’algorithme

Tri par insertion d’une liste de longueur \(n\)

  1. Pour \(i\) variant de 1 à \(n - 1\)

  2. \(\quad \mathtt{inserer}\, \ell[i]\mbox{ dans }\ell[0:i+1]\)

  3. Fin Pour

Un exemple

Le tableau Un tri par insertion montre l’évolution de la tranche triée lors du tri par sélection de la liste des lettres du mot TIMOLEON.

Un tri par insertion

\(i\)

\(\ell\)

1

I TMOLEON

2

IM TOLEON

3

IMO TLEON

4

ILMO TEON

5

EILMO TON

6

EILMOO TN

7

EILMNOO T

Son coût

Notons \(\mathrm{c}_{\mathrm{tri-insert}}(n)\) le nombre de comparaisons d’éléments d’une liste de longueur \(n\) lors du tri par insertion de cette liste.

Compte-tenu de l’algorithme de ce tri, ce nombre est égal à la somme des comparaisons effectuées pour chacune des insertions :

\[\mathrm{c}_{\mathrm{tri-insert}}(n) = \sum_{i=1}^{n-1} \mathrm{c}_{\mathrm{insert}}(i)\]

À la différence du tri par sélection, le nombre de comparaisons va dépendre du contenu de la liste à trier, et compte-tenu de ce qui a été dit pour le coût de l’insertion, il y a lieu de distinguer deux cas :

  • dans le meilleur des cas, la liste est déjà triée, et on est dans le meilleur des cas de l’insertion à chaque étape de la boucle. Et on a ainsi :

    \[\mathrm{c}_{\mathrm{tri-insert}}(n) = \sum_{i=1}^{n-1} 1 = n - 1.\]

  • dans le pire des cas, la liste est triée dans l’ordre inverse et on est alors dans le pire des cas de l’insertion à chaque étape de la boucle. On a alors :

    \[\begin{split}\mathrm{c}_{\mathrm{tri-insert}}(n) &= \sum_{i=1}^{n-1} i\\ &= \frac{n(n - 1)}{2}\\ &\sim \frac{n^2}{2}.\end{split}\]

Ainsi dans le pire des cas, l’algorithme du tri par insertion a le même coût que celui par sélection : il est quadratique en fonction de la longueur de la liste.

Mais dans le meilleur des cas, il est linéaire (degré 1). Le tri par insertion possède de très bonnes performances pour trier des listes presque triées.

Qu’en est-il en moyenne pour des listes quelconques ?

Évolution du nombre de comparaisons dans les tris par sélection et par insertion en moyenne.

La figure ci-contre montre l’évolution du nombre de comparaisons dans les tris par sélection et par insertion en moyenne.

Le calcul de ce nombre moyen a été obtenu en triant 100 fois par insertion des listes générées aléatoirement avec des longueurs comprises entre 1 et 100 et en totalisant les comparaisons effectuées, puis en divisant par 100 ce total. Pour le tri par sélection, comme le nombre de comparaisons ne dépend uniquement de la longueur de la liste, il est inutile de moyenner. (On peut d’ailleurs observer que la courbe correspondant au tri par sélection est lisse, alors que celle du tri par insertion ne l’est pas).

On peut constater qu’en moyenne le tri par insertion est deux fois moins coûteux que le tri par sélection. Et effectivement, on peut prouver qu’en moyenne le nombre de comparaisons du tri par insertion est équivalent à

\[\mathrm{c}_{\mathrm{tri-insert}}(n) \sim \frac{n^2}{4}.\]

Il existe des tris plus performants dont le coût en moyenne, ou dans le pire des cas, n’est pas quadratique mais de l’ordre de \(n\log{n}\). Citons à titre d’exemple le tri rapide (quicksort) et le tri fusion (mergesort).

Il existe aussi des algorithmes de tri qui n’opèrent pas par comparaison d’éléments.

Des tris pour mélanger ?

La question à laquelle nous nous intéressons dans cette partie est en quelque sorte le contraire de celle du tri : le mélange de l’ordre des éléments d’une liste.

En Python, une fonction du module random effectue ce travail : la fonction shuffle. En voici un exemple d’utilisation :

>>> from random import shuffle
>>> l = [1, 2, 3, 4, 5]
>>> shuffle(l)
>>> l
[3, 1, 2, 4, 5]

Comme on peut le constater, cette fonction a pour effet de bord de modifier la liste qu’on lui passe en paramètre. De même que la méthode sort des listes, elle modifie uniquement l’ordre des éléments. Mais contrairement à la méthode sort il est impossible de prévoir l’ordre qui résultera d’un appel à la fonction shuffle : cet ordre est choisi au hasard (random).

Comment la fonction shuffle effectue-t-elle son travail ? Plus généralement, quel(s) algorithme(s) permet(tent) de mélanger l’ordre des éléments d’une liste ? C’est ce que nous allons voir dans la suite.

Un premier algorithme

Voici une première proposition d’algorithme pour mélanger l’ordre des éléments d’une liste.

Mélange des éléments d’une liste (première version)

Entrée : \(\ell\) une liste de longueur \(n\).

Sortie : aucune

Effet de bord l’ordre des éléments de \(\ell\) est modifié de façon aléatoire.

  1. Pour \(i\) variant de \(0\) à \(n-2\)

  2. \(\quad j\leftarrow\) indice choisi au hasard entre \(0\) et n-1

  3. \(\quad \mathtt{echanger}\ \ell[i]\mbox{ et }\ell[j]\)

  4. Fin Pour

Cet algorithme n’est pas déterministe puisqu’il fait appel à des choix effectués au hasard. Il est impossible d’en prévoir le déroulement exact lors de l’une de ses exécutions. Mais on peut néanmoins en décrire toutes les exécutions possibles.

L’arbre qui suit montre tous les déroulements possibles de cet algorithme lorsque la liste \(\ell\) contient trois éléments (ici les trois nombres 1, 2 et 3).

Figure made with TikZ

Arbre des déroulements possibles du premier algorithme de mélange pour la liste [1,2,3]

Explication de cet arbre :

  • À la racine de l’arbre (située tout en haut) figure la liste \(\ell\) dans son état initial.

  • De cette racine partent trois arêtes vers trois nœuds correspondant aux trois états possibles de la liste \(\ell\) après échange à la première étape de la boucle Pour (\(i=0\)). Ces trois états de gauche à droite correspondent aux trois valeurs possibles de la variable \(j\) dans l’ordre 0, 1 et 2.

  • Au niveau suivant, figurent neuf états de la liste. Ils correspondent aux états qu’on obtient depuis l’état précédent lors de l’échange à la seconde étape de la boucle Pour (\(i=1\)).

  • Enfin au niveau le plus bas, les feuilles de l’arbre (qui figurent en grisé), nous obtenons vingt-sept états de la liste tous issus de l’état parent après l’échange de la troisième et dernière étape de la boucle Pour (\(i=2\)). Ces états sont les états finaux possibles de la liste soumise à l’algorithme.

L’examen des 27 feuilles de l’arbre montre que l’algorithme permet d’obtenir chacun des six ordres possibles des éléments d’une liste de longueur trois. Cet algorithme n’écarte donc aucun ordre. Mais si nous comptons pour chacun des six ordres possibles combien de fois on les obtient on établit le tableau suivant :

(1,2,3)

4

(1,3,2)

5

(2,1,3)

5

(2,3,1)

5

(3,1,2)

4

(3,2,1)

4

Ce tableau révèle donc que certains ordres peuvent être obtenus plus souvent que d’autres. L’algorithme de mélange n’est donc pas équitable puisqu’il avantage certains ordres.

Plus généralement, pour une liste de longueur \(n\), le nombre d’ordres possibles des éléments est égal à \(n! = 1\times 2\times 3\ldots\times n\), et le nombre de déroulements possibles de l’algorithme est égal à \(n^n\). L’arbre possède donc \(n^n\) feuilles chacune d’elles correspondant à l’un des \(n!\) ordres. Mais comme pour tout entier \(n\geq 3\), \(n^n\) n’est pas divisible par \(n!\), on en conclut que pour des listes de longueur au moins égale à trois, cet algorithme privilégie certains ordres et n’est donc pas équitable.

Ce dernier point est un grave défaut de cet algorithme, il nous en faut donc un autre.

Un deuxième algorithme de mélange

Pour corriger le défaut du premier algorithme, proposons un second algorithme.

Mélange des éléments d’une liste (seconde version)

Entrée : \(\ell\) une liste de longueur \(n\).

Sortie : aucune

Effet de bord l’ordre des éléments de \(\ell\) est modifié de façon aléatoire.

  1. Pour \(i\) variant de \(0\) à \(n-2\)

  2. \(\quad j\leftarrow\) indice choisi au hasard entre \(i\) et n-1

  3. \(\quad \mathtt{echanger}\ \ell[i]\mbox{ et }\ell[j]\)

  4. Fin Pour

L’arbre ci-dessous montre tous les déroulements possibles de ce second algorithme pour la liste \(\ell = [1,2,3]\).

Figure made with TikZ

Arbre des déroulements possibles du second algorithme de mélange pour la liste [1,2,3]

On le voit, il n’y a que six déroulements possibles, et les six permutations possibles de la liste \(\ell\) sont obtenues chacune une et une seule fois.

On peut prouver que pour une liste de longueur \(n\) l’arbre des déroulements possibles de cet algorithme possède \(n!\) feuilles et que chacune des permutations de la liste est obtenue une et une seule fois. Ce second algorithme est donc meilleur que le premier dans le sens où toutes les permutations de l’ordre des éléments d’une liste peuvent être obtenue, sans que l’une d’elles soient plus fréquemment obtenue qu’une autre.

Remarque sur le second algorithme

Comparons l’algorithme du tri par sélection et celui du second mélange, seules les lignes 3 diffèrent :

  • dans le tri par sélection, la ligne 3 détermine l’indice du plus petit élément de la tranche l[i:n], pour déterminer quel échange effectuer à la ligne 4 ;

  • et dans la seconde méthode de mélange, la ligne 3 consiste à choisi au hasard un indice compris entre i et n-1 pour ensuite faire l’échange de la ligne 4.

La similarité est importante. Notre second mélange est donc un tri par sélection, dans lequel la détermination de l’indice du plus petit élément se fait au hasard.

Il est tout à fait possible de concevoir un algorithme de mélange équitable à partir du tri par insertion. (Exercice)

Liens

Notes

1

Il est d’ailleurs difficile d’expliquer à partir de quand ce nombre est trop important, on retrouve ici le problème de savoir combien il faut de grains de sable pour en faire un tas…

2

On ne voit pas très bien l’intérêt d’un tri de livres selon leur nombre de pages …

3

D’autres algorithmes sont étudiés en seconde année de licence, en particulier des tris récursifs comme le tri rapide ou le tri par fusion.

4

En particulier les tableaux du module numpy.

5

En effet, quel sens donner à l’affirmation cette carotte est plus petite que ce salsifis ?