Algorithmique ii - Tri par dénombrement et par répartition

Le tri par dénombrement.

Le tri par dénombrement, souvent appelé tri linéaire en référence à sa classe de complexité en temps, est un tri qui opère uniquement sur des valeurs entières avec une faible dispertion. La dispertion des valeurs entières dans une liste \(L\) est définie par le ratio \begin{equation} \Delta(L):=1-\frac{\#\{x_i\mid x_i\in L\}}{\max L -\min L + 1} \end{equation} Le numérateur de la fraction est le nombre de valeurs distinctes dans la liste \(L\) et le dénominateur est l'étendue de la liste, i.e. la taille de l'intervalle entier délimité par les valeurs minimale et maximale de la liste \(L\). Nous préciserons dans la section Complexité la raison de cette hypothèse. D'après le résultat du chapitre Complexité des tris comparatifs, nous savons que le tri opère nécessairement sans faire de comparaisons sur les termes de la liste.
Calculez la dispertion de la liste \([1,1,2,3,1,8,1,2,1,1]\) et de la liste \([3,1,1,2]\). Quelle est la dispertion minimale d'une liste ? Quelle est la dispertion maximale d'une liste ? Justifiez.

L'algorithme opère en deux phases. La première phase consiste à parcourir la liste \(L\) afin de dénombrer les occurrences de chaque valeur. Par exemple la liste \(L=[{\color{#FF0}7},3,4,{\color{#FF0}7},4,{\color{#FF0}7}]\) contient une fois la valeur 3, 2 fois la valeur 4 et 3 fois la valeur \({\color{#FF0}7}\). Pour ranger ces nombres d'occurrences, on utilise une table auxiliaire \(H\) qui fait office d'histogramme. L'idéal serait de pouvoir utiliser les valeurs \(v\) comme clés d'indexation de l'histogramme \(H\), mais les tables sont indexées avec des entiers positifs et les valeurs de la liste peuvent être négatives. Il faut donc trouver un palliatif. Il suffit de translater les valeurs \(v\) de \(\delta:= 1 -\min L\) où \(\min L\) est la plus petite valeur dans la liste \(L\) pour que \(\min L\) soit associée à l'index 1. Dans notre exemple la plus petite valeur étant 3, il faut décaler toutes les valeurs de la liste de \(\delta=-2\) positions. Donc \(H=[1_3,2_4,0_5,0_6,3_{\color{#FF0}7}]\) (nous avons indiqué les valeurs correspondantes de la liste en indice). L'exercice suivant propose une autre alternative pour l'indexation.

À l'issue de la première phase, pour chaque valeur \(v\) dans la liste on dispose de son nombre d'occurrences à la position \(v + \delta\) dans l'histogramme \(H\). La deuxième phase consiste à parcourir \(H\) avec une variable d'indexation \(i\) et à ranger exactement \(H[i]\) fois la valeur \(i -\delta\) dans la liste \(L\). Dans notre exemple, \(H=[1_3,2_4,0_5,0_6,3_{\color{#FF0}7}]\), on range donc successivement 1 fois la valeur 3 puis 2 fois la valeur 4 et 3 fois la valeur 7 dans \(L\) pour obtenir la liste triée \(L=[3,4,4,7,7,7]\).

Démontrez que l'ensemble des entiers relatifs \(\mathbf Z\) est équipotent à l'ensemble des entiers naturels \(\mathbf N\) en exhibant une bijection \(\varphi:{\mathbf Z}\rightarrow{\mathbf N}\). Indication : associez les nombres négatifs aux entiers impairs et les nombres positifs aux entiers pairs.

Vous pouvez observer ci-dessous la valeur de l'histogramme pour une liste \(L\) de votre choix (les valeurs \(v\) sont limitées aux entiers \(-15\leq v\leq 15\) pour limiter la taille de l'affichage) :

\(L=[\)\(]\)

Les valeurs de la liste sont comprises entre et . On obtient donc un histogramme \(H\) à entrées :

\(H = [\)\(]\)
Et la liste triée est finalement
\(L = [\)\(]\)

On peut à présent écrire l'algorithme TriDenombrement. Par hypothèse, la liste \(L\) contient des entiers relatifs. Dans un premier temps, il faut trouver la valeur minimale \(\min\) et la valeur maximale \(\max\) dans la liste \(L\) (instruction #8) afin de déterminer l'espace nécessaire pour ranger les nombres d'occurrences dans l'histogramme \(H\). Notons que la recherche de ces deux valeurs peut se faire en une seule passe sur la liste \(L\), il est donc préférable de ne pas faire appel aux fonctions Min et Max des langages de programmation quand elles existent. Il suffit ensuite de parcourir \(L\) une seconde fois pour incrémenter les valeurs de l'histogramme. Dans un deuxième temps, on parcourt cette fois la liste \(H\) et on range chaque valeur \(v := i-\delta \) exactement \(H[i]\) fois dans la liste \(L\).

TriDenombrement(@L)
données
   L: liste d'entiers
variables
   i,j,min,max,delta: entiers
   H: table d'entiers
debut
    (min,max) ← MinMax(L)    
    Allouer(H, max - min + 1, 0)
    delta ← 1 - min
    i ← 1
    TQ (i ≤ #L) FAIRE
       H[L[i] + delta] ← H[L[i] + delta] + 1        
       i ← i + 1
    FTQ
    i ← 1
    j ← 1
    TQ (i ≤ #L) FAIRE
       SI (H[j] > 0) ALORS
          L[i] ← j - delta
          H[j] ← H[j] - 1
          i ← i + 1
       SINON
          j ← j + 1
       FSI
   FTQ
FIN
Il faut bien réaliser que le tri par dénombrement s'appuie explicitement sur le parcours croissant des indices de l'histogramme qui sont par construction déjà rangés selon l'ordre naturel.

Le tri par répartition.

Il s'agit d'une variante du tri par dénombrement qui s'avère plus versatile. Ce tri calque exactement le mode opératoire d'un facteur dans un centre de tri postal. Le facteur dispose d'une armoire de tri (cf. table ci-dessous) constituée d'autant de casiers (de listes) qu'il y a d'adresses dans sa tournée.

123 456 789 10
111213 141516 171819 20
212223 242526 272829 30
313233 343536 373839 40
414243 444546 474849 50
515253 545556 575859 60

Armoire de tri postal schématisée.

Avant de commencer sa tournée, le facteur récupère les enveloppes à distribuer, i.e. les éléments de la liste \(L\)) et range chaque enveloppe \(L[i]\) dans le casier correspondant à l'adresse sur l'enveloppe. Une fois toutes les enveloppes réparties dans les casiers, le facteur n'a plus qu'à les rassembler dans l'ordre des casiers (les concaténer) pour commencer sa tournée.

Bien entendu, le facteur aura au préalable cherché une tournée (un cycle hamiltonien dans le graphe dont les sommets sont les différentes boites aux lettres et les arcs les routes) optimale afin de minimiser la distance à parcourir. C'est un problème à part entière et difficile connu comme le problème du voyageur de commerce, qui sera abordé en master. Une fois une tournée déterminée (optimale ou non, le facteur n'a pas nécessairement suivi un cours d'algorithmique avancée…), les adresses successives sont associées aux casiers dans l'ordre de lecture, de gauche à droite et de haut en bas.

Si la liste est définie sur un ensemble \(V\) quelconque plutôt que sur des entiers, on peut généraliser le tri en se donnant une fonction d'adressage \(\text{adr}:V\rightarrow{\mathbf N}\) qui va renvoyer l'adresse \(\text{adr}(v)\) du casier dans lequel il faut ranger la valeur \(v\) de la liste. Si la liste contient des entiers naturels, il suffit de choisir comme fonction d'adressage, l'application identique \(v\mapsto v\).

L'écriture de l'algorithme de répartition des mots de la liste à l'aide des casiers ne pose aucune difficulté particulière. Notons que nous travaillons directement sur la liste en entrée qui est vidée au fur et mesure que ses éléments sont répartis dans les différents casiers. Après la répartition, la liste \(L\) est vide et on la reconstitue en concaténant les casiers dans l'ordre naturel. On peut bien entendu réaliser la même opération en renvoyant une liste différente de celle d'entrée. L'intérêt de cette écriture est que cette répartition se fait in situ. L'algorithme auxiliaire Enfiler(L,x) rajoute l'élément \(x\) au bout de la liste \(L\), opération que l'on peut toujours réaliser en \(\Theta(1)\) avec une structure ad hoc. L'algorithme auxiliaire Concaténer(L,L') concatène deux listes et cette opération peut elle aussi être réalisée avec un coût constant \(\Theta(1)\). Le chapitre Listes, piles, files étudie précisément les questions de complexité liées à l'utilisation du modèle de données liste selon les multiples structures que l'on peut lui associer.

TriRépartition(@L,adr);
données
   L: liste d'entiers
   adr: fonction d'adressage
variables
   Casiers: liste 
   amin,amax,valeur: entiers
debut
    amax ← Max(L,adr)    
    Allouer(Casiers, amax, [])
    i ← 1
    TQ (i ≤ #L) FAIRE
       valeur ← Defiler(L);
       Enfiler(Casiers[adr(L,i)],valeur)
       i ← i + 1
    FTQ
    i ← 1
    TQ (i ≤ #Casiers) FAIRE
       L ← Concaténer(L,Casiers[i]);
       i ← i + 1
   FTQ
FIN
On peut utiliser le tri par répartition pour trier une liste de mots définis sur un alphabet \(A:=\{a_1,a_2,\ldots,a_q\}\) en fonction de leurs longueurs avec la fonction d'adressage \(\text{adr}:u\mapsto |u|\). On peut également les trier selon leur \(k\)-ème lettre \(a_i\) avec la fonction d'adressage \(\text{adr}:u\mapsto i\) si \(u_k=a_i\), ce que vous pouvez observer ci-dessous pour une liste \(L\) de mots de votre choix suivant la clé de tri \(k:=\) de votre choix également.

\(L=[\)\(]\)

Voici le contenu des différents casiers rangés par construction dans l'ordre alphabétique de manière à ce que leur concaténation réalise le tri de la liste (le casier \(C\) contient les mots dont la longueur est inférieure à la valeur \(k\) que vous aurez saisie) :

Si la liste ne contient que des mots de longueurs \(1\), le tri par répartition réalise un tri alphabétique.
Nous utiliserons le tri par répartition avec deux fonctions d'adressages distinctes dans le chapitre Tri lexicographique afin de trier plus rapidement une liste de mots qu'avec un algorithme de tri conventionnel.

Complexité

Commençons par l'algorithme TriDenombrement. Notons \(n:=\#L\) la taille de la liste considérée. Le calcul du minimum et du maximum coûte une passe sur la liste, soit \(\Theta(n\)) et l'allocation de l'histogramme \(\Theta(m)\) où \(m\) désigne l'étendue de la liste \(L\). La construction de l'histogramme demande une nouvelle passe sur la liste et à donc un coût de \(\Theta(n)\). La reconstruction de la liste dans la boucle #18 est facile à analyser globalement, on vide chacun des \(H[i]\) et on sait que \[\sum_{i=1}^{\max L - \min L +1}H[i] = n\] donc la reconstruction de la liste coûte elle aussi \(\Theta(n)\). L'analyse de la complexité de l'algorithme TriRéparition est identique si l'on suppose que l'appel de la fonction d'adressage \(\text{adr}\) a un coût constant \(\Theta(1)\). On en conclut le théorème :

La complexité de l'algorithme TriDenombrement et de l'algorithme TriRéparition pour une liste \(L\) de taille \(n\) et d'étendue \(m\) est \begin{equation} T(n,m)=\Theta(n+m). \end{equation} en supposant que la fonction d'adressage a un coût constant.
Ces algorithmes ne sont donc linéaires que si la taille \(m\) de l'histogramme reste raisonnable \(O(n)\) au regard de la taille de la liste, autrement dit quand la dispertion est faible et dans ce cas \(T(n,m)=\Theta(n)\). C'est la dispertion qui conditionnera l'utilisation ou non de ces tris.

Quelle serait la complexité en espace de l'algorithme si l'on avait utilisé la bijection \(\varphi:{\mathbf Z}\rightarrow{\mathbf N}\) de l'exercice 1 ?

Travaux pratiques

Écrivez la fonction MinMax(L) qui renvoie le minimum et le maximum de la liste \(L\) en une seule passe. Écrivez une fonction TriDenombrement(L) qui effectue le tri de la liste \(L\) à l'aide de l'algorithme du tri par dénombrement.
Écrivez une fonction TriRépartition(L,a) qui effectue le tri de la liste \(L\) pour la fonction d'adressage \(a\) à l'aide de l'algorithme du tri par répartition. Testez votre fonction pour trier une liste de mots suivants leur \(k\)-ème caractère.
[Solution en C]
[Solution en Python]