Tri lexicographique

L'ordre lexicographique

Introduction

Nous avons déjà observé que trier des objets suppose que l'on dispose d'une relation d'ordre définie sur ces objets et qui plus est totale. Nous avons majoritairement utilisé l'ordre naturel pour il­lus­trer les algorithmes de tri.

Il n'est pas rare que l'on ait à trier des listes d'objets disposants de plusieurs attributs. Considérons par exemple une liste de couples \((T,P)\) contenant une température \(T\) (en degrés Celsius) et une pression \(P\) (en Pascals). En limitant la précision des mesures à un entier, ces deux attributs sont munis de la relation d'ordre naturel. On peut trier une telle liste selon la température ou la pression, mais dans ce cas l'autre attribut est tout bonnement ignoré dans le tri et ce n'est pas ce que l'on souhaite.

Une première idée consiste à comparer les couples terme à terme, autrement dit on définit une relation \(\mathscr \preceq\) sur l'ensemble des couples \((T,P)\) par : \begin{equation} (T,P)\preceq(T',P')\ \iff\ (T\leq T')\ \wedge\ (P\leq P'). \end{equation} On vérifie aisément que cette relation est réflexive, anti-symétrique et transitive, il s'agit de l'ordre produit. Cette relation se généralise à des \(n\)-uplets d'un produit cartésien \(E_1\times E_2\times\cdots\times E_n\) d'en­sem­bles totalement ordonnés \((E_i,\leq_i)\). Malheureusement cette relation d'ordre n'est que partielle, en effet on ne peut pas comparer les couples \((4,3)\) et \((2,5)\) par exemple. Une autre cons­truc­tion est nécessaire.

Une réponse possible à ce problème est la relation d'ordre lexicographique. C'est celle que nous utilisons pour ranger les mots dans un dictionnaire ou pour classer les nombres réels quand ils sont représentés à l'aide de leurs développements décimaux. L'idée est naturelle, on part d'une liste \(L\) de \(n\)-uplets d'un produit cartésien \(E_1\times E_2\times\cdots\times E_n\) d'ensembles totalement ordonnés \((E_i,\leq_i)\) et on trie cette liste une première fois suivant la première composante. On partitionne alors la nouvelle liste \(L\) en sous-listes contiguës selon la valeur de la première composante (leur concaténation est donc la liste \(L\)). On trie alors chacune de ces sous-listes à l'aide d'un algorithme de tri stable suivant la seconde composante. On recommence le même procédé sur chacune de ces sous-listes pour la composante suivante, etc.

Considérons la liste \(L=((2,2,c),(3,2,b),(1,3,c),(3,2,a),(3,1,c),(1,2,a))\) dé­fi­nie sur le produit cartésien \({\mathbb N}\times{\mathbb N}\times{\mathscr A}\) où \({\mathbb N}\) est muni de l'ordre naturel et \({\mathscr A}\) est l'al­pha­bet latin muni de l'ordre alphabétique. UnLe ré­sul­tat dépend de la mé­thode de tri choisie puis­qu'il ex­is­te plu­sieurs tri­plets de mê­me pre­miè­re valeur. premier tri suivant la première composante en­tiè­re pourrait fournir la liste \[\underbrace{(\textcolor{yellow}{1},3,c),(\textcolor{yellow}{1},2,a)}_{A_{\textcolor{yellow}{1}}},\underbrace{(\textcolor{yellow}{2},2,c)}_{B_{\textcolor{yellow}{2}}},\underbrace{(\textcolor{yellow}{3},2,b),(\textcolor{yellow}{3},2,a),(\textcolor{yellow}{3},1,c)}_{C_{\textcolor{yellow}{3}}}.\] Un second tri stable de ces trois listes suivant la deuxième composante pourrait donner : \[\underbrace{\overbrace{(\textcolor{yellow}{1},\textcolor{orange}{2},a)}^{A_{\textcolor{yellow}{1},\textcolor{orange}{2}}},\overbrace{(\textcolor{yellow}{1},\textcolor{orange}{3},c)}^{A_{\textcolor{yellow}{1},\textcolor{orange}{3}}}}_{A_{\textcolor{yellow}{1}}\ \text{triée}},\underbrace{\overbrace{(\textcolor{yellow}{2},\textcolor{orange}{2},c)}^{B_{\textcolor{yellow}{2},\textcolor{orange}{2}}}}_{B_{\textcolor{yellow}{2}}\ \text{triée}},\underbrace{\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{1},c)}^{C_{\textcolor{yellow}{3},\textcolor{orange}{1}}},\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},b),(\textcolor{yellow}{3},\textcolor{orange}{2},a)}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2}}}}_{C_{\textcolor{yellow}{3}}\ \text{triée}}.\] Et un dernier tri stable sur la liste \(C_{\textcolor{yellow}{3},\textcolor{orange}{2}}\) suivant la dernière composante (les 4 premières listes ne contiennent plus qu'un élément) achèverait le processus : \[(\textcolor{yellow}{1},\textcolor{orange}{2},a),(\textcolor{yellow}{1},\textcolor{orange}{3},c),(\textcolor{yellow}{2},\textcolor{orange}{2},c),(\textcolor{yellow}{3},\textcolor{orange}{1},c),\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{a})}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{a}}},\overbrace{(\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{b})}^{C_{\textcolor{yellow}{3},\textcolor{orange}{2},\textcolor{#AAAAFF}{b}}}.\]

Notons dès à présent que la méthode de tri présentée dans l'exemple ci-dessus n'est pas des plus simple à cause des segmentations successives des listes manipulées. Nous verrons à la section suivante comment faire mieux. D'autre part, l'ordre lexicographique tel qu'il vient d'être présenté n'est pas aussi général que celui que nous connaissons de longue date, les mots d'un dictionnaire ou les développements décimaux des nombres réels ne sont pas nécessairement de même longueur.

Formalisation

On rappelle que si \(\leq\) est une relation d'ordre, alors \(<\) désigne l'ordre strict associé à \(\leq\). On va définir une relation d'ordre sur la réunion de produits cartésiens finis d'ensembles totalement ordonnés.

Soit \((E_i,\,\leq_i)_{i\in{\mathbb N}}\) une famille d'ensembles totalement ordonnés et \begin{equation} \label{eq:defprodinf} E:=\bigcup_{k\in{\mathbb N}}\prod_{i=1}^kE_i. \end{equation} Soit \((n,m)\in{\mathbb N}\times{\mathbb N}\) et \(x=(x_1,\ldots,x_n)\in E\) et \(y=(y_1,\ldots,y_m)\in E\). On note \(p:=\min\{n,m\}\). La relation \(\preceq\) définie sur \(E\) par \(x \preceq y\) si et seulement si : \begin{equation}\small \label{eq:condtl} {\color{#BB0}\Big(\exists k\in\ab{1}{p}\ \;\big((\forall i\in\llbracket 1,k\llbracket\ \;(x_i=y_i)\big)\wedge(x_k <_k y_k)\Big)}\;\vee\; {\color{#AAF}\Big((p\leq m)\wedge\big(\forall i\in\ab{1}{p}\ \;x_i=y_i\big)\Big)} \end{equation} est une relation d'ordre total appelée ordre le­xi­co­gra­phi­que.

La disjonction \((\ref{eq:condtl})\) exprime formellement que \(x\preceq y\) si et seulement s'il existe un rang \(k\) en deça duquel tous les termes de \(x\) et \(y\) sont égaux et tel que \(x_k < y_k\) ou que \(x\) est un préfixe de \(y\).

Démontrez le théorème dans sa version simplifiée où \(E\) est le produit fini de \(n\) ensembles totalement ordonnés \((E_i,\leq_i)_{i\in[1,n]}\).

En pratique l'ordre lexicographique est utilisé sur des \(E_i\) tous identiques et munis de la même relation d'ordre, par exemple \(E_i=\{0,1,2,\ldots,9\}\) muni de l'ordre naturel pour les dé­ve­lop­pe­ments décimaux illimités dans la représentation des nombres réels. Dans la suite nous nous intéresserons plus particulièrement aux mots d'un langage. Le formalisme est légèrement différent de celui que nous venons de présenter.

Un mot de \(k\) lettres, au sens usuel du terme, étant une suite de \(k\) lettres, il n'y a pas de gros efforts à faire pour transposer le concept dans le langage mathématique. Pour cela, on se donne un ensemble fini \(A=\{a_1,\ldots,a_{q}\}\) appelé alphabet à \(q\) éléments \(a_i\) appelés lettres (ou symboles). Par convention on suppose que cet alphabet est muni d'une relation d'ordre total \(\preceq\) héritée de l'ordre naturel via l'application bijective et croissante \(a\) : \[\forall (i,j)\in{\ab{1}{q}}\times{\ab{1}{q}},\quad i \leq j\ \Leftrightarrow a_i\preceq a_j.\] Toute suite finie (ou séquence) \(u\) de symboles de \(A\) définit un mot et on appelle longueur du mot le nombre de ses symboles noté \(|u|\) ou \(\#u\). Pour parfaire le modèle, on ne sépare pas les symboles de la suite et on écrira tout simplement \(tranches\) pour la suite de symboles \(t,r,a,n,c,h,e,s\). On note \(A^*\) l'ensemble (infini) de tous les mots possibles (qui remplace \(E\) dans la définition \((\ref{eq:defprodinf})\)). On équipe \(A^*\) d'une loi de composition interne, la concaténation que l'on note comme un produit et qui associe à deux mots \(u\) et \(v\) le mot \(u.v\) constitué des lettres de \(u\) suivies par les lettres de \(v\). Cette loi est associative et l'ajout d'un élément neutre \(\epsilon\) appelé mot vide font de \(A^*\) un monoïde. Il s'agit de la fermeture de Kleene de \(A\).

Si l'alphabet \(A = \{0,1\}\) alors \(A^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 100, ...\}\). Si l'alphabet \(A=\{a,b,\ldots,z\}\) est l'alphabet latin, la concaténation bon.jour des mots bon et jour est le mot bonjour (qui est différent de \(jourbon\), la loi n'est bien sûr pas commutative.)

Nous ne fournissons pas d'exemples de comparaisons de deux mots selon l'ordre lexicographique (confondu avec l'ordre alphabétique dans le langage courant), l'expérience du lecteur en la matière devrait suffire. L'objectif de cette section est de comprendre la formalisation à partir de la con­nais­san­ce pratique et non l'inverse.

Un algorithme

La relation d'ordre étant à présent total, on peut toujours comparer deux mots \(u=u_1u_2\ldots u_n\) et \(v=v_1v_2\ldots v_m\) de \(A^*\), on aura donc \(u\leq v\) ou \(v < u\), ce qui se traduit par 3 situations :

  1. \(u = v\),
  2. \(u < v\),
  3. \(u > v\).

Le Théorème-Définition suggère comment écrire l'algorithme. La première phase consiste à comparer terme-à-terme les symboles \(u_i\) et \(v_i\) de \(u\) et \(v\) en partant du premier symbole et avancer tant qu'ils sont identiques et qu'il reste des symboles à comparer. Plusieurs cas sont alors possibles en sortant de cette boucle~:

  1. On n'a atteint ni la fin de \(u\) ni celle de \(v\). Dans ce cas on peut décider si \(u < v\) ou \(v > u\) en comparant \(u_i\) et \(v_i\) suivant l'ordre alphabétique.
  2. On a atteint la fin de l'un des deux mots, disons \(u\) (le raisonnement est symétrique si c'est \(v\)). Dans ce cas, \(u\) est préfixe de \(v\) et on a \(u\leq v\) et on peut décider si c'est \(u < v\) ou \(u=v\) selon qu'on a atteint ou non la fin de \(v\) également.

L'algorithme ci-dessous renvoie l'une des trois valeurs \(-1\), \(0\) ou \(1\) selon que \(u < v\), \(u=v\) ou que \(u>v\), respectivement.

ComparaisonLexico(u,v):{-1,0,+1}
données
   u, v: listes de caractères
variables
   i: entier
DEBUT
   i ← 1
   TQ ((i ≤ |u|) ET (i ≤ |v|) ET (u[i] = v[i]) FAIRE
      i ← i + 1
   FTQ   
   SI ((i > |u|) ET (i > |v|)) ALORS
      renvoyer  0 u = v
   SINON SI ((i > |u|) OU ((i ≤ |v|) ET (u[i] < v[i]))) ALORS
      renvoyer -1 u < v
   SINON SI ((i > |v|) OU ((i ≤ |u|) ET (u[i] > v[i]))) ALORS
      renvoyer +1  u > v
   FSI
FIN

NB. Il faut noter que la justesse de l'algorithme dépend de l'hypothèse (toujours discutable) que l'interprétation d'une formule conjonctive (resp. disjonctive) s'arrête dès qu'une condition n'est pas satisfaite (resp. satisfaite).

Faites une preuve d'arrêt de cet algorithme. Démontrez que l'algorithme est valide.

Complexité

Nous allons évaluer la complexité de l'algorithme en fonction du nombre de comparaisons entre les lettres des deux mots. Notons \(n:=|u|\) et \(m:=|v|\). Dans le meilleur des cas, la première lettre suffit pour conclure, ainsi \(\check T(n,m)=\Theta(1)\) et dans le pire des cas il faut parcourir toutes les lettres du mot le plus court donc \(\hat T(n,m)=\Theta(\min\{n,m\})\).

Le cas moyen, comme toujours, est plus délicat à obtenir. On suppose que \(n\leq m\) et on partitionne l'ensemble \(E\) des instances de tailles \(n,m\) en fonction du nombre de lettres à comparer pour décider, ce nombre variant entre \(1\) et \(n+1\), en effet, on tient compte de la situation où \(u\) est un préfixe strict de \(v\) auquel cas il faut une comparaison supplémentaire pour conclure, même s'il n'y a pas à proprement parler de lettre dans le mot le plus court. Notons \(E_k\) la partie de \(E\) contenant toutes les instances qui nécessitent \(k\) comparaisons, \(1\leq k\leq n+1.\) On a \begin{equation}\label{eq:compmoyenne} \bar T(n,m)=\frac{1}{\#E}\sum_{k=1}^{n+1}k.\#E_k \end{equation} Si l'alphabet est de taille \(q\) alors \(\#E=q^{n+m}\) puisqu'il s'agit du nombre de couples de mots de tailles \(n\) et \(m\) possibles. Dénombrons les ensembles \(E_k\) pour \(1\leq k\leq n\), le cas particulier de la partie \(E_{n+1}\) où \(u\) est un préfixe de \(v\) sera traité à part. Si la décision est prise en comparant \(u_k\) et \(v_k\) pour \(1\leq k\leq n\), cela signifie que les mots \(u\) et \(v\) ont un préfixe commun de \(k-1\) lettres et que \(u_k\not=v_k\). Le mot \(u\) est arbitraire, on a donc \(q^{n}\) possibilités pour \(u\). Les \(k-1\) premières lettres de \(v\) sont fixées par celles de \(u,\) la \(k\)-ème lettre \(v_k\) doit être distincte de \(u_k\) et les \(m-k\) restantes sont quelconques, soit \((q-1)q^{m-k}\) possibilités pour constituer \(v\), finalement: \begin{equation}\label{eq:Ek} \forall k,\ 1\leq k\leq n,\quad \#E_k = q^{n+m-k}(q-1). \end{equation} Il reste à calculer \(\#E_{n+1}\). Dans ce cas \(u\) est préfixe de \(v\) et il y a \(q^m\) possibilités pour constituer \(v\) (mais une seule pour \(u\)), donc \begin{equation}\label{eq:En} \#E_{n+1} = q^m \end{equation} Notons, en guise de vérification, que la somme des cardinaux des \(E_k\) est bien le cardinal de \(E\): \begin{align*} \#E_{n+1}+\sum_{k=1}^{n+1}\#E_k &=q^m+\sum_{k=1}^{n}q^{n+m-k}(q-1)\\ &=q^m+q^m(q-1)\sum_{k=1}^{n}q^{n-k}\\ &=q^m+q^m(q-1)\frac{q^n-1}{q-1}\\ &=q^{n+m}\\ &=\#E \end{align*} On peut remplacer les valeurs \(\#E_k\) déterminées en (\ref{eq:Ek}) et (\ref{eq:En}) dans l'expression (\ref{eq:compmoyenne}) pour obtenir \begin{equation}\label{eq:compfinale} \bar T(n,m) = \frac{(n+1)}{q^n} + (q-1)\underbrace{\color{yellow}\sum_{k=1}^{n}kq^{-k}}_{\color{yellow}S(q^{-1})} \end{equation} Et comme on devait s'y attendre, l'expression montre que la complexité ne dépend que de la plus petite des deux longueurs, ici \(n\) par hypothèse. Il reste à évaluer la somme \(\color{yellow}S(q^{-1})\) et on applique la même preuve que celle du Lemme prouvé au chapitre Fonctions de complexité  :

\(S(q^{-1})= \displaystyle\frac{q^{n+1}-q(n+1)+n}{q^n(q-1)^2}\)

Puisque la complexité ne dépend que de la longueur du plus petit mot, on peut alors conclure

La complexité moyenne de la comparaison lexicographique entre deux mots de longueurs \(n\) et \(m\) est \begin{equation} \label{trilexasympt} \bar T(n,m) = \frac{q}{q-1}-\frac{1}{q^{\min\{n,m\}}(q-1)} \end{equation}
NB. Il faut déduire de l'équation \((\ref{trilexasympt})\) que la moyenne du nombre de comparaisons entre lettres est asymp­to­ti­que­ment égale à \(\frac{q}{q-1}\).

Algorithme du tri lexicographique

Présentation

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 les 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 longueurs différentes). 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 \(L\) en fonction de leur deuxième lettre. En lisant la table suivante de la gauche vers la droite, on peut suivre l'évolution du contenu de cette liste et des différents casiers \(C_{\alpha}\) (ceux qui ne sont pas utilisés sont omis), au fur et à mesure de l'avancement du tri par répartition. Le symbole \(\color{yellow}\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 \(C_{\alpha}\) (y compris les casiers vides qui ne sont pas montrés) 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_ku_{k+1}\ldots u_l\) si \(k\leq l\) et le mot vide \(\varepsilon\) si \(k > 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)\). Soit \(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 de mots de longueurs différentes, on commence par répartir les mots de la liste \(L\) dans \(l\) listes \(L_k,\ k\in[1,l]\) suivant leurs longueurs, les mots de longueur \(k\) étant rangés dans la liste \(L_k\). Cette opération est réalisée encore une fois par l'algorithme TriRépartition selon la longueur des mots. À l'issue de ce partitionnement la liste \(L\) est vide.

Le tri consiste toujours à effectuer \(l\) tris par répartition des mots de \(L\) selon les symboles d'indice \(l\) à \(1\). La seule différence avec le tri lexicographique de mots de même longueur consiste, avant d'effectuer le prochain tri par répartition à l'indice \(k\), à insérer les mots de la liste \(L_k\) au début de la liste \(L\). Ainsi avant le premier tri par répartition sur les symboles à la position \(k=l\), on insère la liste \(L_l\) à gauche de la liste \(L\), autrement dit la nouvelle liste \(L\) est obtenue par concaténation de la liste \(L_k\) et de l'ancienne liste \(L\).

Pourquoi faut-il réaliser la concaténation \(L_k.L\) et pas \(L.L_k\) avant chaque tri par répartition ?
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, en partant de \(k=l\) jusqu'à \(k=1\).

TriLexico(@L):liste
données
   L: liste de mots
variables
   P: liste   la partition en L_k
   k: entier
debut
   P ← Partition(L)
   k ← #P    #P = l
   TQ k > 0 FAIRE
      Concaténer(P[k],L)
      TriRépartition(L,(u,k) ↦ j)  u_k = a_j
      k ← k - 1
   FTQ
fin
La fonction d'adressage \((u,k)\mapsto{\color{yellow}j}\) utilisée à instruction #12 est celle qui renvoie le numéro \({\color{yellow}j}\) de la \(k\)-ème lettre \(u_k\) du mot \(u\), i.e. telle que \(u_k=a_{\color{yellow}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\) est égale à \[n_{m}+n_{m-1}+\cdots+n_{m-k+1}\] et 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 une fonction Python PPL(u, v) qui renvoie 0 si \(u=v\), -1 si \(u < v\) et 1 si \(u > v\).

É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]