Présentation du problème
Nous avons déjà fait observer que trier des objets suppose implicitement que l'on dispose d'une relation d'ordre et qui plus est totale. Nous avons majoritairement utilisé l'ordre naturel pour illustrer 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')\Longleftrightarrow (T\leq T')\ \text{et}\ (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'ensembles 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,2017)\) et \((8,1789)\) par exemple. Une autre construction 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 sur place suivant la seconde composante. On recommence le même procédé sur chacune de ces sous-listes pour la composante suivante, etc.
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 au chapitre suivant 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.
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\).
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éveloppements 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[1,q]\times[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\).
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 connaissance 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 :
Commençons par le cas le plus simple. Si les deux mots \(u\) et \(v\) sont de même longueur, le premier théorème suggère une simple boucle pour décider quelle est la situation rencontrée. On compare terme-à-terme les symboles \(u_i\) et \(v_i\) de \(u\) et \(v\) en partant du premier symbole d'index \(i=1\). Tant que \(u_i=v_i,\) on avance (\(i\leftarrow i +1\)) ; sinon \(u_i < v_i\) ou \(v_i < u_i\) soit respectivement \(u < v\) ou \(v < u\).
Si les longueurs sont différentes, l'algorithme est sensiblement le même et l'adaptation est fournie par le second théorème. Le processus diffère uniquement si l'un des deux mots est un préfixe de l'autre. Dans ce cas la boucle qui permet de comparer les symboles \(u_i\) et \(v_i\) atteint le dernier symbole du mot le plus court ce qui permet d'affirmer qu'il est le plus petit des deux mots (au sens de l'ordre lexicographique).
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.
ALGORITHME ComparaisonLexico(u,v):{-1,0,+1}
données
u,v: listes de caractères
variables
i,p: entiers
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).
Complexité
Nous allons évaluer la complexité en fonction du nombre de comparaisons entre 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é :
Puisque la complexité ne dépend que de la longueur du plus petit mot, on peut alors conclure
Travaux pratiques
Écrivez une fonction Python PPL(u, v) qui renvoie 0 si \(u=v,\) -1 si \(u < v\) et 1 si \(u > v\).
[Solution en C]