Algorithmique ii - Tri lexicographique

Présentation de l'algorithme.

On reprend les notations du chapitre Ordre lexicographique dans lequel nous avons défini une relation d'ordre totale sur l'ensemble \(A^*\) des mots sur un alphabet fini \(A:=\{a_1,a_2,\ldots,a_{q}\}\). Le tri par dénombrement n'est pas adapté à la situation, entre autres.Nous sommes en mesure d'appliquer la plupart des algorithmes de tri que nous avons déjà étudiés en remplaçant une liste de nombres par une liste de mots et l'ordre naturel par l'ordre lexicographique. Cependant, la nature particulière des objets à trier va nous permettre de développer une méthode plus adaptée, sous entendu plus rapide.

Supposons pour le moment que la liste de mots à trier contienne uniquement des mots de même longueur \(l\), nous verrons plus loin comment généraliser le processus à des listes de mots de longueur variable. Nous allons appliquer l'algorithme du tri par répartition TriRépartition \(l\) fois sur la liste \(L\) en triant successivement les mots de la liste selon leur \(k\)-ème lettre pour \(k\) variant de \(l\) à \(1\) (voir l'exemple). Commençons par étudier un exemple élémentaire avec la liste de quatre mots \(L=[le,as,os,ai]\) de longueur \(l=2\).

Dans un premier temps nous trions les mots de la liste en fonction de leur deuxième lettre. La table suivante montre l'évolution du contenu de la liste \(L\) et des casiers au fur et à mesure de l'avancement du tri par répartition. Le symbole \(\bullet\) indique où va être rangé le prochain mot de la liste :

\begin{align*} &\ 0 & &\ 1 & &\ 2 & &\ 3 & &\ 4 \\ L&=[l{\color{yellow}e},as,os,ai] & L&=[a{\color{yellow}s},os,ai] & L&=[o{\color{yellow}s},ai] & L&=[a{\color{yellow}i}] & L&=[\;]\\ C_{\color{yellow}e} &= [{\color{yellow}\bullet}] & C_e&=[le] & C_e&=[le] & C_e&=[le] & C_e&=[le]\\ C_i &= [\;] & C_i&=[\;] & C_i&=[\;] & C_{\color{yellow}i}&=[{\color{yellow}\bullet}] & C_i&=[ai]\\ C_s &= [\;] & C_{\color{yellow}s}&=[{\color{yellow}\bullet}] & C_{\color{yellow}s}&=[as,{\color{yellow}\bullet}] & C_s&=[as,os] & C_s&=[as,os] \end{align*}
Tri par répartition de la liste \(L=\{le,as,os,ai\}\) suivant la 2ème lettre.

La concaténation des casiers fournit une nouvelle liste \(L=[le,ai,as,os]\). On recommence de la même façon mais la comparaison se fait cette fois sur la première lettre :

\begin{align*} &\ 0 & &\ 1 & &\ 2 & &\ 3 & &\ 4 \\ L&=[{\color{#46F}l}e,ai,as,os] & L&=[{\color{#46F}a}i,as,os] & L&=[{\color{#46F}a}s,os] & L&=[{\color{#46F}o}s] & L&=[\;]\\ C_a&=[\;] & C_{\color{#46F}a}&=[{\color{#46F}\bullet}] & C_{\color{#46F}a}&=[ai,{\color{#46F}\bullet}] & C_a&=[ai,as] & C_a&=[ai,as] \\ C_{\color{#46F}l}&=[{\color{#46F}\bullet}] & C_l&=[le] & C_l&=[le] & C_l&=[le] & C_l&=[le]\\ C_o&=[\;] & C_o&=[\;] & C_o&=[\;] & C_{\color{#46F}o}&=[{\color{#46F}\bullet}] & C_o&=[os] \end{align*}
Tri par répartition de la liste \(L=\{le,ai,as,os\}\) suivant la 1ère lettre.

Maintenant que toutes les lettres ont été comparées, la concaténation des casiers fournit la liste triée \[L=[ai,as,le,os].\] Il peut sembler paradoxal de commencer par la dernière lettre plutôt que la première, mais la preuve du lemme suivant fournit l'explication. Pour faciliter la compréhension, quand nous ferons référence à la \((-k)\)-ème lettre d'un mot \(u=u_1u_2\ldots u_l\in A^l\), il s'agira de la \(k\)-ème lettre en partant de la fin du mot, ainsi \(u[-1]=u[l]\) et plus généralement \(u[-k]=u[l-k+1]\). D'autre part, on désigne par \(u[k:\;]\) le suffixe \(u_iu_{i+1}\ldots u_l\) si \(i\leq l\) et le mot vide \(\varepsilon\) si \(i>l\). On a donc en particulier \(u[1:\;]=u\).

Soit \(L\) une liste de mots de même longueur \(l > 0\). À l'issue des \(l\) tris par répartition de la liste suivant les clés de tri décroissantes \(k=l\) à \(k=1\), les mots de la liste \(L\) sont triés dans l'ordre lexicographique.
Soit \(k\leq l\). Dans cette preuve uniquement, on désignera par \(L_{k}\) la liste obtenue après le \(k\)-ème tri par répartition sur la \((-k)\)-ème lettre et \(S_{k}\) la liste des suffixes \(u[-k:\;]\) des mots de \(L_{k}\). On a \(L_0=L\) et \(S_{l}=L_{l}\). Nous allons prouver par récurrence que la liste \(S_{l}\) est triée. Soit \(P(k)\) le prédicat :
après le \(k\)-ème tri par répartition, la liste \(S_{k}\) est triée

La liste \(S_{1}\) contient uniquement la dernière lettre de chacun des mots de la liste \(L\) après le premier tri par répartition donc \(P(1)\) est vraie puisqu'il s'agit du tri alphabétique. Soit \(k < l\). À l'étape \(k+1\) l'algorithme TriRépartition trie les mots de la liste \(L_{k}\) suivant la prochaine lettre à la position \(-(k+1)\). Soient \(u\) et \(v\) deux mots de la liste \(L_k\). Notons \(a_i\) et \(a_j\) leurs \((-(k+1))\)-ème lettre respectivement. Puisque le \((k+1)\)-ème tri par répartition se fait sur cette lettre, trois situations se présentent :

  1. Si \(i < j\), l'algorithme range le mot \(u\) dans le casier \(i\) et le mot \(v\) dans le casier \(j\). Le mot \(u\) précède donc le mot \(v\) après la concaténation des casiers.
  2. Si \(i > j\), le raisonnement est symétrique et le mot \(u\) suit donc le mot \(v\) après la concaténation des casiers.
  3. Si \(i = j\) et \(u[-k\!:\;]\preceq v[-k\!:\;]\) alors \(u\) est placé avant \(v\) dans la liste \(L_k\) d'après l'hypothèse de récurrence \(P(k)\), l'algorithme rangera donc \(u\) avant \(v\) dans le casier \(i\) et \(u\) sera placé avant \(v\) après la concaténation des casiers. Le raisonnement est symétrique si \(v[k\!:\;]\preceq u[k\!:\;]\).
Dans les trois cas, à l'issue du \(k+1\) tri, les suffixes \(u[-(k+1)\!:\;]\) et \(v[-(k+1)\!:\;]\) sont rangés dans la liste \(S_{k+1}\) conformément à la définition de l'ordre lexicographique, donc \(P(k+1)\) est vraie.

À ce stade, nous ne sommes en mesure de trier que des mots de même longueur. Notons \(l\) la longueur maximale des mots de la liste \(L\). Pour généraliser l'algorithme à une liste quelconque, on commence par répartir les mots de la liste \(L\) dans des listes \(L_k\) selon leur longueur \(k\). Cette opération sera évidemment réalisée encore une fois par l'algorithme TriRépartition selon les longueurs des mots. À l'issue de ce partitionnement la liste \(L\) est donc vide. On achève alors le tri en procédant quasiment de la même manière que dans le cas où les mots sont de même longueur en concaténant la liste \(L_k\) à la liste \(L\) avant la répartition selon la \((-k)\)-ème lettre.

Modifiez l'algorithme TriRépartition pour écrire un algorithme Partition qui partitionne la liste \(L\) en listes \(L_k\) des mots de longueurs \(k\) et renvoie la liste \(P\) de ces listes. Calculez la complexité de cet algorithme.

Observons le processus de partionnement avec la liste (vous pouvez saisir les mots de votre choix) :

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

Il ne reste plus à présent qu'à articuler les deux opérations. L'algorithme opère donc en deux phases. La première phase partitionne la liste initiale \(L\) en \(l\) listes \(L_k\) contenant tous les mots de longueur \(k\in [1\!:\!l]\). La seconde phase applique \(l\) fois l'algorithme du tri par répartition selon la \((-k)\)-ème lettre des mots, de \(k=l\) à \(k=1\).

TriLexico(@L):liste
données
   L: liste de mots
variables
   P: liste   la partition en L_k
   i: entier
debut
   P = Partition(L)
   i ← #P    #P = l
   TQ i > 0 FAIRE
      Concaténer(L,P[i])
      TriRépartition(L,(u,i) ↦ j)  u_i = a_j
      i ← i - 1
   FTQ
fin
La fonction d'adressage \((u,i)\mapsto j\) utilisée à instruction #12 est celle qui renvoie le numéro \(j\) de la \(i\)-ème lettre \(u_j\) du mot \(u\), i.e. telle que \(u_i=a_j\).

Complexité

On rappelle que \(q:=\#A\). On note \(n:=\#L\) la longueur de la liste à trier, \(n_i:=\#L_i\) la longueur de la liste des mots de longueur \(i\) et \(l\) la longueur du mot le plus long. On a \begin{equation}\label{eq:sumlongueurs} \sum_{i=1}^ln_i=n. \end{equation}

L'algorithme Partition demande \(\Theta(n)\) opérations pour calculer la longueur maximale \(m\) (instruction #9) puis \(\Theta(m)\) opérations pour initialiser les \(m\) listes \(L_i\) (instructions #11 à #14). La répartition des \(n\) mots dans les \(l\) casiers a un coût en \(\Theta(n)\), on a donc \begin{equation} T_{\textsf{Partition}}(n,l)=\Theta(n) + \Theta(l) \end{equation}

L'algorithme TriRépartition a un coût de \(\Theta(q)\) pour initialiser les \(q\) casiers à la liste vide, un coût de \(\Theta(\nu)\) pour répartir les \(\nu\) éléments de la liste d'appel et un coût de \(\Theta(q)\) pour concaténer les \(q\) casiers, soit au total \begin{equation} T_{\textsf{Répartition}}(\nu,q)=\Theta(\nu) + \Theta(q) \end{equation} Pour évaluer la complexité de l'algorithme TriLexico, il nous reste à calculer le coût des \(l\) appels successifs à l'algorithme de tri par répartition (instruction #12) pour chacune des \(l\) listes \(L_k\). Le \(k\)-ème appel se fait sur une liste dont la longueur \(\nu=n_{m}+n_{m-1}+\cdots+n_{m-k+1}\) donc majorée par la longueur \(n\) de la liste initiale d'après (\ref{eq:sumlongueurs}), soit \(O(n)\). On peut à présent conclure : \begin{align*} T_{\textsf{TriLexico}}(n,l,q) &=\Theta(n) + \Theta(l)\quad\text{(instruction #8)}\\ &\ +l\Theta(1)\quad\text{(instructions #10, #11 et #13)}\\ &\ +l(O(n)+\Theta(q))\quad\text{(instruction #12)}\\ &=O(ln) + \Theta(lq) \end{align*} Le cardinal de l'alphabet étant constant et la longueur maximale \(l\) des mots étant asymptotiquement négligeable devant la taille de la liste, on peut conclure que

La complexité de l'algorithme du tri lexicographique TriLexico en fonction du nombre \(n\) de mots à trier est \begin{align*} T_{\textsf{TriLexico}}(n)=\Theta(n). \end{align*}

Travaux pratiques

Écrivez les fonctions Python Partition(L), TriRepartition(L) et TriLexico(L). Écrivez une fonction GenListe(n,l) qui renvoie une liste de \(n\) mots de longueur \(\leq l\) choisis aléatoirement. Comparez le temps d'exécution pour trier une liste avec vos fonctions et la fonction de tri de Python.

[Solution en C]
[Solution en Python]