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 listes de valeurs entières avec une faible dispersion, quantité définie par \begin{equation} \Delta(L):=1-\frac{\#\{x_i\mid x_i\in L\}}{\text{max}\,L -\text{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 ma­xi­ma­le de la liste \(L\). Nous préciserons dans la section Complexité la raison de cette hypothèse. D'après ce théorème sur la complexité des tris comparatifs, nous savons que si ce tri a une complexité linéaire, il opère nécessairement sans faire de comparaisons sur les termes de la liste.
Calculez la dispersion de la liste \([1,1,2,3,1,8,1,2,1,1]\) et de la liste \([3,1,1,2]\). Quelle est la dispersion minimale d'une liste ? Quelle est la dispersion maximale d'une liste ? Justifiez.

L'algorithme opère en deux phases. La première phase consiste à parcourir la liste \(L\) afin de dé­nom­brer 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*.(*) Un histogramme est une table contenant le nombre d'occurences de chaque valeur d'une liste triée, la va­leur servant de clé d'en­trée de la table. 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 -\text{min}\, L\) où \(\text{min}\, L\) est la plus petite valeur dans la liste \(L\) pour que \(\text{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'oc­cur­rences à 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 \(\text{min}\,\) et la valeur ma­xi­ma­le \(\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 ha­mil­to­nien 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\) à la fin 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 struc­tu­res que l'on peut lui associer. L'algorithme Eteter(L) renvoie l'élément au début de la liste et l'élimine de la liste. 

TriRépartition(@L,adr)
données
   L: liste d'élément de V
   adr: fonction d'adressage V → N
variables
   Casiers: tableau de listes
   amax, i: entiers
   v: élément de V
debut
    amax ← Max(L,adr)    
    Allouer(Casiers, amax, [])
    TQ (L != []) FAIRE
       v ← Eteter(L);
       Enfiler(Casiers[adr(v)], v)
    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'adres­sage \(\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 à la position \(k:=\).

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

Voici le contenu des différents casiers rangés par construction dans l'ordre al­pha­bé­ti­que 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.
Le tri par répartition est stable.
Deux éléments de la liste dont le \(k\)-ème terme pointe à la même adresse \(a\) par la fonction d'adressage sont enfilés dans le casier \(a\) et restent donc placés dans le même ordre l'un par rapport à l'autre après la concaténation des différents casiers.

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 - \text{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 dispersion est faible et dans ce cas \(T(n,m)=\Theta(n)\). C'est la dispersion 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

(1) Écrivez la fonction void MinMax(tliste L, int *min, int *max) qui cherche le minimum et le maximum de la liste \(L\). La fonction doit faire en une seule passe.

(2) Écrivez une fonction tliste Histogramme(tliste L) qui renvoie l'histogramme des valeurs contenues dans la liste \(L\). Le nombre d'occurences de la valeur minimale doit être rangée à l'index 0 de l'histogramme à l'aide d'une translation (cf. cours).

(3) Enfin, écrivez une fonction void TriDenombrement(tliste L) qui effectue le tri de la liste \(L\) à l'aide de l'algorithme du tri par dénombrement.

Indication : le type tliste est une structure C contenant un tableau et sa taille.

(4) Comparez la complexité moyenne du tri par dénombrement avec celle du tri par tas em­pi­ri­que­ment en traitant des listes de type permutations aléatoires d'ordre \(n\). Pour cela, tracez la courbe représentative de la fonction comptant le nombre d'accès à un terme d'une liste (\(L\) ou histogramme) pour le tri par dénombrement et celle de la fonction comptant le nombre de comparaisons pour le tri par tas avec gnuplot.

Pour générer une liste de type permutation aléatoire, utilisez cette suggestion d'un précédent TP.

Utilisez les déclarations suivantes pour gérer les listes chainées : 
typedef struct TCELL{
  int valeur;
  struct TCELL *suiv;  
} TCELL;

typedef TCELL *TLISTE;
(1) Écrivez les fonctions TLISTE *InsQueue(TLISTE *L, int valeur) et TLISTE *InsTete(TLISTE *L, int valeur) qui rajoutent respectivement la valeur entière valeur à la queue et à la tête de la liste chaînée L, et renvoient cette nouvelle liste. NB. La liste L peut-être initialement vide (NULL).

(2) Écrivez une fonction TLISTE SupTete(TLISTE *L) qui renvoie la liste ne contenant que la cellule en tête de la liste L en la supprimant de cette liste. Écrivez une fonction TLISTE Rabouter(TLISTE L1, L2) qui concatène la liste L2 à la liste L1 et renvoie cette liste (on ne crée donc pas de nouvelle liste. il n'y a aucune cellule créée.

(3) Écrivez une fonction TLISTE *Repartir(TLISTE *L) qui renvoie un tableau de listes chaînées indexé par les valeurs entières (à une translation près) contenues dans la liste L et qui répartit les différentes cellules L dans les listes correspondantes du tableau. La liste L doit donc être vide à la fin de la répartition.

(4) À l'aide des fonctions précédentes, écrivez une fonction void TriRepartition(TLISTE L) qui réalise le tri par répartition.