Complexité des tris comparatifs - Algorithmique II

Tous les algorithmes de tri que nous avons étudiés jusqu'ici s'appuient sur la comparaison des valeurs de la liste/tableau entre elles pour les trier, on parle donc de tri comparatif. Nous avons vu que la complexité des tris dits empiriques est quadratique alors que le tri par tas est linéarithmique \(\Theta(n\,\log n)\). La question naturelle qui émerge des études de complexité que nous avons menées est : Quelle est la complexité minimale dans le pire des cas d'un tri comparatif ? Nous allons montrer que cette complexité ne peut être meilleure que \(\Omega(n\,\log n)\).

Pour pouvoir comparer les éléments d'une liste, il faut que ses termes soient comparables au sens où ils appartiennent à un ensemble \(E\) ordonné. Nous supposerons donc que l'ensemble \(E\) est muni d'une relation d'ordre notée \(\preceq\) et qu'il s'agit plus précisément d'une relation d'ordre total.

Le lemme et les exercices qui suivent montrent d'une part que l'on ne perd pas en généralité en ne considérant que des listes à valeurs entières et d'autre part que l'on peut également se limiter à des listes qui sont des permutations. L'idée est que du point de vue de l'ordre, on peut remplacer dans une liste \(L\) de \(n\) éléments d'un ensemble totalement ordonné \((E,\preceq)\) chacune des \(n\) valeurs par sa position dans la liste triée de \(L\). On remplace donc l'ordre total \(\preceq\) qui équipe \(E\) par l'ordre naturel \(\leq\) qui équipe \(\mathbb N\) sans perturber les comparaisons entre éléments. Par exemple, toute comparaison entre deux éléments de la liste de nombres réels \([\pi,\,2.5,\,e,\,1.3]\) pour l'ordre lexicographique a la même valeur de vérité que la comparaison correspondante dans la liste d'entiers naturels \([4,\,2,\,3,\,1]\) pour l'ordre naturel.

Soit \(L\) une liste de taille \(n\) à valeurs dans un ensemble totalement ordonné \((E,\preceq)\). Alors il existe une permutation \(\sigma\in{\frak S}_n\) telle que \begin{equation}\label{eq:permimp} \forall (i,j)\in [1,n]^2,\quad \sigma(i) \leq \sigma(j) \Rightarrow L[i] \preceq L[j]. \end{equation} Si la liste ne contient que des valeurs distinctes alors il s'agit d'une équivalence dans \((\ref{eq:permimp})\).

Démontrons la première partie, l'autre est laissée en exercice. Puisque l'ordre est total, on peut ordonner les \(n\) termes de la liste \(L\) dans l'ordre croissant, autrement dit il existe (au moins) une permutation \(s\in{\frak S}_n\) telle que \begin{equation}\label{eq:omega} \forall i\in[1,n-1],\quad L[s(i)]\preceq L[s(i+1)]. \end{equation} Par induction, on en déduit que \begin{equation}\label{eq:omega2} \forall (i,j)\in[1,n]^2,\quad i\leq j\Rightarrow L[s(i)]\preceq L[s(j)]. \end{equation} autrement dit l'application \(L\circ s:[1,n]\rightarrow E\) est croissante. Comme \(s\) est une bijection, notons \(\sigma:=s^{-1}\) la permutation réciproque. On peut alors réécrire \((\ref{eq:omega2})\) : \begin{equation}\label{eq:omega3} \forall (i,j)\in[1,n]^2,\quad \sigma(i)\leq \sigma(j)\Rightarrow L[i]\preceq L[j]. \end{equation}

Soit \(E=\{x_1,x_2,\ldots,x_n\}\) un ensemble totalement ordonné. Montrez qu'il existe une unique bijection croissante entre l'ensemble \(E\) et l'ensemble \(\{1,\ldots,n\}\) muni de la relation d'ordre naturel. Démontrez qu'une liste \(L\) d'éléments d'un ensemble \(E\) totalement ordonné est triée si et seulement si \(L\) est une application croissante.

Pour ne pas compliquer inutilement l'exposé nous pouvons légitimement nous limiter à l'étude des listes \(L\) qui sont des permutations de \({\frak S}_n\) où \(n\) désigne la taille de la liste \(L\).

À chaque fois qu'une structure de contrôle est rencontrée dans l'exécution d'un algorithme, son exécution peut être déroutée vers autant de blocs d'instructions différents que la structure en gère (si/alors/sinon, tant que, switch, etc.) Par analogie avec le comportement humain, on dit que l'algorithme prend une décision. On modélise l'ensemble des conditions rencontrées par un algorithme ainsi que les décisions qui en découlent par un arbre enraciné appelé arbre de décision. Chaque condition est représentée par un nœud auquel on associe autant de branches qu'il y a de décisions possibles. La racine de l'arbre contient la première condition rencontrée. Dans le cas particulier d'un algorithme de tri comparatif, une décision est prise en fonction du résultat d'une comparaison, il s'agit donc d'un arbre de décision binaire :

Le choix gauche/négatif et droit/positif est bien sûr arbitraire. Observons les différentes comparaisons \(T[i] > T[i + 1]\) effectuées par l'algorithme TriBulles du tri à bulles ainsi que l'évolution du tableau pour les \(3!=6\) instances de taille \(n=3\) : \begin{align*} (1)\quad &1,2,3\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}1,2,3\stackrel{\color{#F84}T[2]\leq T[3]}{\color{#F84}\longrightarrow}1,2,3\\ (2)\quad &1,3,2\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}1,3,2\stackrel{\color{#8F4}T[2]>T[3]}{\color{#8F4}\longrightarrow}1,2,3\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}1,2,3\\ (3)\quad &2,1,3\stackrel{\color{#8F4}T[1]>T[2]}{\color{#8F4}\longrightarrow}1,2,3\stackrel{\color{#F84}T[2]\leq T[3]}{\color{#F84}\longrightarrow}1,2,3\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}1,2,3\\ (4)\quad &2,3,1\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}2,3,1\stackrel{\color{#8F4}T[2]>T[3]}{\color{#8F4}\longrightarrow}2,1,3\stackrel{\color{#8F4}T[1]>T[2]}{\color{#8F4}\longrightarrow}1,2,3\\ (5)\quad &3,1,2\stackrel{\color{#8F4}T[1]>T[2]}{\color{#8F4}\longrightarrow}1,3,2\stackrel{\color{#8F4}T[2]>T[3]}{\color{#8F4}\longrightarrow}1,2,3\stackrel{\color{#F84}T[1]\leq T[2]}{\color{#F84}\longrightarrow}1,2,3\\ (6)\quad &3,2,1\stackrel{\color{#8F4}T[1]>T[2]}{\color{#8F4}\longrightarrow}2,3,1\stackrel{\color{#8F4}T[2]>T[3]}{\color{#8F4}\longrightarrow}2,1,3\stackrel{\color{#8F4}T[1]>T[2]}{\color{#8F4}\longrightarrow}1,2,3\\ \end{align*}

Nous indiquons dans chaque nœud interne de l'arbre de décision, la comparaison \(T[i] > T[i + 1]\) réalisée et l'instance traitée par l'algorithme dans chacune des 6 feuilles. Le chemin qui mène de la racine à une feuille/instance permet de suivre les différentes comparaisons effectuées pour la trier.

C'est l'arbre de décision associé à un tri qui va nous permettre d'établir une borne sur la complexité.

La liste \(L\) de taille \(n\) à trier est confondue avec la permutation sous jacente de \(\frak S_n\). Un algorithme de tri doit être en mesure trier toutes les permutations \(L\) possibles soit \(n!\) permutations distinctes. Montrons que deux permutations distinctes ont nécessairement des feuilles distinctes dans l'arbre de décision. Que l'algorithme s'effectue in situ ou non, si l'on note \(L\) la liste d'entrée et \(I\) la liste de sortie triée, autrement dit l'identité de \({\frak S}_n\), l'algorithme construit implicitement la permutation inverse de \(L\) i.e. la permutation \(\sigma\in\frak S_n\) telle que \(\sigma\circ L = I\). Si l'on suppose que deux listes \(L\) et \(L'\) sont représentées par la même feuille dans l'arbre de décision, cela signifie que les instructions exécutées par l'algorithme sont strictement identiques dans les deux cas, autrement dit qu'il réalise la même permutation \(\sigma\). On a par conséquent \(\sigma\circ L=I=\sigma\circ L'\) et la permutation \(\sigma\) étant une bijection on en conclut que \(L=L'\).

Le nombre de comparaisons effectuées pour trier une liste \(L\) de taille \(n\) est par construction la longueur (i.e. le nombre d'arcs) du chemin qui relie la racine de l'arbre de décision à la feuille associée à \(L\). Le pire des cas pour un algorithme de tri comparatif correspond donc au chemin le plus long dans son arbre de décision, c'est-à-dire à la hauteur \(h\) de l'arbre. Nous devons donc évaluer quelle est la longueur minimale de ce chemin. Autrement dit, il faut construire un arbre contenant au moins \(n!\) feuilles et dont la hauteur \(h(n)\) soit minimale. Un arbre binaire de hauteur \(h\) contient au plus \(2^h\) feuilles, maximum atteint par un arbre binaire équilibré et complet. La hauteur \(h(n)\) doit donc satisfaire l'inégalité suivante~: \begin{equation}\label{eqtricom1} 2^{h(n)}\geq n! \end{equation} soit \begin{equation}\label{eqtricom2} h(n)\geq \sum_{i=1}^n\log_2 i. \end{equation} On minore classiquement cette somme par une intégrale en rappelant que la primitive de \(\ln x\) est \(x\,\ln x -x\) ou en faisant une intégration par parties pour le retrouver :: \begin{align*} \sum_{i=1}^{n}\log_2 i &=\sum_{i=2}^{n}\log_2 i\\ &\geq \frac{1}{\ln 2}\int_{1}^{n}\ln x\, dx\\ &=\frac{1}{\ln 2}\left[x\ln x -x\right]_{1}^{n}\\ &\geq n\log_2 n-\frac{n}{\ln 2} \end{align*} Ce qui achève la démonstration.