Analyse des tris empiriques

Généralités

Nous allons revisiter les trois algorithmes de tri empiriques abordés en première année, à savoir le tri par sélection, le tri par propagation (plus com­munément appelé tri à bulles) et le tri par insertion. Ces trois algorithmes trient des listes statiques (ou tableaux). Autrement dit, ils se contentent de mo­di­fier le contenu des cellules de ces listes pour y par­venir. A contrario, d'autres algorithmes de tri opèrent sur des listes dynamiques, c'est-à-dire qu'ils sont susceptibles d'ajouter ou de retirer des termes, en tête ou en queue de liste ou encore à des positions arbitraires. Ces déclinaisons du modèle de données liste sont liées à des structures de données dif­fé­ren­tes dans les langages de pro­gram­ma­tion qui ont un impact majeur dans la com­ple­xi­té des algorithmes réalisant les opé­ra­tions usuelles sur les listes, insertion, suppression, appartenance, etc. Ces questions seront abor­dées plus en détail dans le chapitre Listes, files, piles.

Soit \(L\) une liste d'éléments d'un ensemble \(X\). Si l'on munit \(X\) d'une relation d'ordre total \(\preceq\) appelée clé de tri, un algorithme qui trie \(L\) à l'aide de comparaisons entre élé­ments de \(L\) pour la clef \(\preceq\) est dit comparatif.
Dans la littérature, une clé de tri fait souvent référence à un champ particulier d'un enregistrement, chaque champ de l'enregistrement étant muni d'une relation d'ordre.

Les algorithmes de tri peuvent posséder des propriétés re­mar­qua­bles :

Un algorithme de tri qui utilise \(O(1)\) mémoire pour ses variables autres que ses paramètres pour trier une liste est dit sur place ou in situ.

En d'autres termes, si l'on distingue les paramètres de l'algorithme des autres variables qui lui sont nécessaires pour réaliser le tri, la taille mémoire occupée par ces dernières est constant quelle que soit la taille de la liste à trier.

Un algorithme de tri qui ne modifie pas la position relative de deux termes égaux pour la clef de tri dans cette liste est dit stable.

Pour mieux comprendre cette propriété, il suffit d'imaginer que les différentes occurrences d'une même valeur sont numérotées (virtuellement) dans l'ordre de leur apparition dans la liste et de s'assurer qu'après le tri la suite de ces numéros est toujours croissante. Par exemple pour la valeur \(2\) qui apparaît trois fois dans la liste \[({\color{yellow}2_1},{\color{#88F}3_1},4,1,5,{\color{yellow}2_2},6,{\color{#88F}3_2},{\color{yellow}2_3}),\] un tri stable pour l'ordre naturel renverrait la liste \[(1,{\color{yellow}2_1},{\color{yellow}2_2},{\color{yellow}2_3},{\color{#88F}3_1},{\color{#88F}3_2},4,5,6),\] alors qu'un tri instable pourrait renvoyer, par exemple, la liste \[(1,{\color{yellow}2_1},\underbrace{{\color{yellow}2_3},{\color{yellow}2_2}}_{\rightleftharpoons},\underbrace{{\color{#88F}3_2},{\color{#88F}3_1}}_{\rightleftharpoons},4,5,6).\]

Cette caractéristique peut s'avérer importante lorsque l'on effectue plusieurs tris successifs à partir d'une liste initiale où chaque nouveau tri s'effectue suivant une clé de tri différente. Un tri stable permet de trier une liste déjà triée en conservant le classement précédent dans chaque sous-groupe d'éléments de même valeur pour la nouvelle clé de tri. Par exemple, supposons que l'on dispose d'une liste d'individus triés dans l'ordre croissant de leur taille que l'on trie une seconde fois, mais selon l'ordre croissant de leur poids cette fois. Avec un tri stable, les groupes d'individus de même poids, contigus dans la liste nouvellement triée, restent triés dans l'ordre croissant de leur taille (un couple (taille, poids) code un individu dans la liste) : \begin{align*} &\ \ \big((175,65),(160,75),(175,45),(165,50),(150,45),(160,45),(150,50)\big)\\ \text{Tri #1: clé taille}\ \mapsto&\ \ \big((150,45),(150,50),(160,75),(165,45),(165,50),(175,65),(175,45)\big)\\ \text{Tri #2: clé poids}\ \mapsto&\ \ \big((\underline{150},{\color{yellow}\underset{=}{45}}),(\underline{160},{\color{yellow}\underset{=}{45}}),(\underline{175},{\color{yellow}\underset{=}{45}}),(\underline{150},{\color{#88F}\underset{=}{50}}),(\underline{165},{\color{#88F}\underset{=}{50}}),(175,65),(160,75)\big)\\ \end{align*}

Les trois algorithmes empiriques se font in situ, le tri par propagation et le tri par insertion sont stable alors que le tri sélection ne l'est pas.

C'est l'étude de leurs fonctions de comp­le­xi­té qui justifie que l'on revienne sur ces trois algorithmes, en particulier la complexité moyenne relativement difficile à établir et hors programme en première année. Dans toute la suite, la liste à trier est notée \(L\) et elle est indexée de \(1\) à \(n\) où \(n\) est un entier naturel qui désigne sa taille, i.e. le nombre de termes qu'elle contient. Nous désignons par \(L[i\colon j]\) la sous-liste constituée des éléments de la liste \(L\) dont les indices sont dans l'intervalle \[ \ab{i}{j}=\{k\in{\mathbf N}\mid i\leq k\leq j\}. \] Attention donc à ne pas faire la confusion avec les intervalles semi-ouverts à droite \([i\colon j]\) du langage Python. Comme ces trois tris s'appuient fondamentalement sur des comparaisons entre les termes de la liste, nous éva­lue­rons parfois leurs complexités en nous concentrant sur ce nombre de com­pa­rai­sons en né­gli­geant les autres pour ne pas compliquer inutilement l'exposé.

Les illustrations interactives des algorithmes utilisent des listes d'entiers relatifs (donc muni de l'ordre naturel), mais il faut garder à l'esprit que ces al­go­ri­thmes s'appliquent à n'importe quelles données d'un ensemble to­ta­le­ment ordonné, le symbole \(\leq\) désignant gé­né­ri­que­ment la re­la­tion d'or­dre considérée. Même dans le cas où les données sont des \(k\)-uplets composites et où la relation d'ordre n'est pas totale, les différentes composantes sont généralement munies d'une relation d'ordre totale.

Ces trois algorithmes opèrent en échangeant le contenu de deux cellules dans le tab­leau, nous ferons donc appel à l'algorithme Echanger qui nécessite une variable auxiliaire pour conserver tem­po­rai­re­ment le contenu d'une des deux cellules  et dont la fonction de complexité notée \(T_{\leftrightarrows}\) est constante \(\Theta(1)\) : 

Echanger(L,i,j)
données
   L: liste de valeurs
   i,j: entiers
variables
   aux: entier
debut
   aux ← L[i]
   L[i] ← L[j] 
   L[j] ← aux
FIN

Dans les calculs de complexité des tris, nous supposerons souvent que la liste \(L\) à trier contient les \(n\) premiers entiers naturels, autrement dit que l'application sous-jacente \(L:\ab{1}{n}\rightarrow \ab{1}{n}\) est une per­mu­ta­tion du groupe symétrique \({S}_n\). Cette hypothèse ne restreint pas la généralité comme nous le verrons dans le cha­pi­tre suivant. L'algorithme Echanger(L,i,j) qui échange les valeurs de la liste aux positions \(i\) et \(j\) définit dont la transposition \((L[i],L[j])\).

On rappelle qu'une inversion d'une permutation \(\sigma\in{S}_n\) est un couple \((i,j)\in\ab{1}{n}^2\) tel que \(i < j\) et \(\sigma(i) > \sigma(j)\). Notons \({\mathscr I}(\sigma)\) l'ensemble des inversions d'une permutation \(\sigma\) de \({\frak S}_n\), i.e. \begin{equation}\label{eq:ensinversions} {\mathscr I}(\sigma):=\big\{(i,j)\in\ab{1}{n}^2\ \mid\ (i < j)\ \wedge\ (\sigma(i) > \sigma(j))\big\} \end{equation}

On considère la liste \(L=[1,2,4,5,6,3,7,9,8,10]\). Vérifiez qu'il s'agit bien d'une permutation de \({S}_{10}\) et calculer \({\mathscr I}(L)\). Combien d'inversions compte cette liste ? Calculez la liste \(L\circ(8,9)\). Combien d'inversions compte-t-elle ?

Le résultat suivant nous sera utile pour le tri à bulles et le tri par insertion. Si, pour ordonner une liste, on échan­ge deux termes contigus dont les indices forment une inversion, alors on diminue ex­ac­te­ment le nombre d'in­ver­sions de la liste par 1.

Soit \(\sigma\in{\frak S}_n\) et \(k\in\ab{1}{n-1}\) tels que \((k,k+1)\in{\mathscr I}(\sigma).\) Alors \begin{equation} \#{\mathscr I}(\tau\circ\sigma)=\#{\mathscr I}(\sigma)-1. \end{equation} où \(\tau\) désigne la transposition \((\sigma(k),\sigma(k+1))\).
Soit \((i,j)\in\ab{1}{n}^2\) tel que \(i < j\) et notons \(\sigma':={\color{#F84}\tau}\circ\sigma\). Nous allons étudier le statut (inversion ou non) de \((i,j)\) pour \(\sigma\) et \(\sigma'\), autrement dit de manière imagée avant et après l'échan­ge des termes \(\color{#F84}\sigma(k)\) et \(\color{#F84}\sigma(k+1)\) opérés par la transposition \(\color{#F84}\tau:=(\sigma(k),\sigma(k+1))\)  : \begin{equation} \begin{matrix} &1 & 2 & 3 & \cdots &k&&k+1&\cdots&n-1&n\\ \sigma\phantom{'}:&\sigma(1)&\sigma(2)&\sigma(3)&\cdots& {\color{#F84}\sigma(k)}&{\color{#F84}>}&{\color{#F84}\sigma(k+1)}&\cdots&\sigma(n-1)&\sigma(n)\\ \sigma':&\sigma(1)&\sigma(2)&\sigma(3)&\cdots& {\color{#F84}\sigma(k+1)}&{\color{#F84}<}&{\color{#F84}\sigma(k)}&\cdots&\sigma(n-1)&\sigma(n) \end{matrix} \end{equation} Si les deux indices \(i\) et \(j\) avec \(i < j\) sont différents de \(k\) et \(k+1\), le statut de \((i,j)\) ne change pas de \(\sigma\) à \(\sigma'\) puisque \(\sigma'(i)=\sigma(i)\) et \(\sigma'(j)=\sigma(j)\). Le statut ne peut éventuellement changer que si l'un au moins des deux indices appartient à \(\{k,k+1\}\). On partitionne l'ensemble \[\big\{(i,j)\in\ab{1}{n}^2\mid (i < j) \wedge (\{i,j\}\cap\{k,k+1\}\not=\varnothing)\big\}\] de la manière suivante (preuve en exercice ci-dessous) :

Dans le premier cas, le couple \((k,k+1)\) qui définissait une inversion pour la permutation \(\sigma\) n'est plus une inversion pour la permutation \(\sigma'\) par construction, il y a donc à ce stade une inversion de moins dans \({\mathscr I}(\sigma')\). Les deux derniers cas étant symétriques, nous ne traitons que le cas 2. Pour tout \(i\in[1,k[\), si \((i,k)\) (resp. \((i,k+1)\) change de statut alors \((i,k+1)\) (resp. \((i,k+1)\) également puisque \(\sigma'(k)=\sigma(k+1)\) et \(\sigma'(k+1)=\sigma(k)\), rétablissant ainsi le nombre d'inversions.

Le corollaire suivant est direct, si \(\#{\mathscr I}(\sigma\circ\tau)=\#{\mathscr I}(\sigma)-1\) où \(\sigma\in S_n\) et \(\tau\) est une transposition de type \((\sigma(k),\sigma(k+1))\), il faut au moins appliquer \(\#{\mathscr I}(\sigma)\) échanges pour obtenir la permutation identité qui n'a aucune inversion.

Un algorithme de tri qui opère en échangeant uniquement des valeurs contiguës d'une liste/permutation \(L\) doit en réaliser au moins \(\#{\mathscr I}(L)\).

Dans la preuve du lemme, vérifiez que les 5 parties définies par les conditions 1, 2i, 2ii, 3i et 3ii constituent bien une partition de l'ensemble des couples \((i,j)\in\ab{1}{n}^2,\ i < j\) tels que \((\sigma'(i),\sigma'(j))\not=(\sigma(i),\sigma(j))\).
En reprenant les notations du lemme et de sa preuve, trouvez une permutation \(\sigma\) de \({\frak S}_4\) telle qu'après la transposition \((\sigma(i),\sigma(j))\) de deux termes non-contigus d'indices \((i,j)\) constituant une in­ver­sion, la permutation \(\sigma'\) ainsi obtenue vérifie \(\#{\mathscr I}(\sigma')-\#{\mathscr I}(\sigma)>1.\)

Le tri par sélection

Présentation de l'algorithme

Le tri par sélection est l'un des tris les plus simples. Il s'appuie sur un algorithme auxiliaire de re­cher­che du minimum (ou symétriquement du maximum) dans une liste \(L\) (supposée non-vide). Pour cette recherche, on initialise toujours le minimum (ou le maximum) au premier terme de la liste puis on parcourt le reste des termes de la liste en mettant à jour la valeur minimale (ou maximale) si le terme courant est plus petit (ou plus grand) : 

Min(L):valeur
données
   L: liste de valeurs
variables
   i: entier
   min: valeur
debut
   min ← L[1]
   i ← 2
   TQ (i ≤ #L) FAIRE
      SI (L[i] < min) ALORS
         min ← L[i]
      FSI 
      i ← i + 1       
   FTQ
   RENVOYER min
FIN

La condition de la boucle #10 ne dépend que de la variable \(i\) qui n'est modifiée que par l'inc­ré­men­ta­tion de l'instruction #14. Si la liste ne contient qu'un seul élément, on n'entre pas dans la boule et l'algorithme s'arrête en renvoyant le minimum qui a été initialisé à la seule valeur de la liste. Sinon, la valeur initiale de \(i\) est inférieure ou égale à la taille de la liste \(L\) et croit strictement à chaque passage dans la boucle ce qui assure que la condition \(i \leq \#L\) échouera pour la valeur \(i=n+1\). L'assertion la variable \(min\) contient la valeur minimale de la liste \(L[1,i-1]\) est vraie à l'entrée de la boucle et il est facile de montrer qu'elle le reste après chaque itération à la ligne #14, la variable contient donc bien la valeur minimale de la liste à la sortie de la boucle puisque \(i=n\), ce qui prouve la validité de l'algorithme.

Adaptez l'algorithme pour écrire un algorithme Max\(\;(L)\) de recherche du maximum dans une liste \(L\). Calculez la complexité de cet algorithme en fonction de la taille \(n\) de la liste \(L\).
On considère l'algorithme de recherche d'un minimum (ou d'un maximum).
  1. Pourquoi est-il toujours préférable d'initialiser le minimum ou le maximum à la première valeur de la liste plutôt qu'à une valeur fixe ?
  2. Peut-on remplacer le test \(L[i] < \text{min}\) par le test \(L[i] \leq \text{min}\) à la ligne #11 ?
  3. Qu'est-ce que cela changerait en terme de complexité ?
  4. Quelle comparaison est alors préférable ?
Écrivez un algorithme IdxMin\(\;(L,g,d)\) qui renvoie la plus petite position du minimum des valeurs de la sous-liste \(L[g\colon d]\) où \((g,d)\in[1,\#L]^2\) et \(g\leq d\), plutôt que le minimum, au­tre­ment dit le plus petit entier \(i_{\min}\in\ab{g}{d}\) tel que \[L[i_{\min}]=\min_{i\in\ab{g}{d}}\{L[i]\}.\]

D'après l'exercice ci-dessus, on sait calculer une position \(i_{\text{min}}\) d'un minimum dans la liste \(L[1:n]\). Pour trier la liste, il suffit de l'échanger avec le premier élément de la liste (\(L[1] \leftrightarrows L[i_{\text{min}}]\)) et de recommencer le processus avec la sous-liste \(L[2:n]\)) et ainsi de suite jusqu'à ce que la sous-liste à parcourir soit réduite à un élément. Il faut noter la symétrie de ce tri, on peut également chercher une plus grande valeur dans la liste et la ranger en dernière position.

L'écriture de l'algorithme coule de source, il suffit de répéter la recherche de l'indice du minimum (instruction #10), de faire l'échange (instruction #11) et de recommencer un cran plus loin dans la liste (incrément de l'indice de départ dans la liste, instruction #12) : 

TriSelection(@L)
données
   L: liste de valeurs
variables
   i,imin,n: entiers
debut
   i ← 1
   n ← #L
   TQ (i < #L) FAIRE
     imin ← IdxMin(L,i,#L)
     Echanger(L,i,imin)    
     i ← i + 1        
   FTQ
FIN

La trace de l'exécution du TriSelection pour la liste \(L=[\)\(]\) ci-dessous permet de comprendre le processus. Chaque ligne représente une étape dans la recherche du minimum, il est distingué des autres valeurs par un fond clair, la valeur à laquelle il est comparé est encadrée et apparaît sur fond rouge dans le cas où elle est inférieure à la valeur minimale, indiquant ainsi qu'il faudra mettre à jour l'indice \(i_{\text{min}}\). Ces mises à jour ainsi que les \(n-1\) échanges réalisés, sont spé­ci­fiés dans la dernière colonne.

Trouvez un contre-exemple qui prouve que le tri par sélection n'est pas un tri stable.

Complexité du tri par sélection

Nous allons estimer la complexité de l'algorithme TriSelection en évaluant tout d'abord celle de l'al­gor­i­thme IdxMin. Elle dépend des indices \(g\) et \(d\), le nombre d'opérations est pro­por­tion­nel au nombre de cellules à parcourir dans le liste \(L\), soit \(d-g+1\). Le nombre réel d'opérations à réaliser dépend bien entendu du nombre de mises à jour de l'indice du minimum fonction de l'instance considérée, mais le coût unitaire est borné par deux constantes donc en \(\Theta(1)\). Comme l'appel à cet al­go­ri­thme se fait toujours pour la valeur \(d=n\), on a

\[T_{\small\text{IdxMin}}(n,d)=\Theta(n-d+1)=\Theta(n-d).\]

Les deux algorithmes Echanger et IdxMin ont tous deux un coût qui ne dépend que de la taille des don­nées à traiter et pas de la nature des instances de taille \(n\), par conséquent les trois complexités dans le meilleur des cas, le pire des cas et le cas moyen se confondent.

Toutes les instructions hors de la boucle tant que de l'algorithme TriSelection ont un coût constant \(\Theta(1)\) et les trois instructions dans la boucle ont pour coûts respectifs \(\Theta(n-d)\), \(\Theta(1)\) et \(\Theta(1)\), on en déduit la somme : \begin{align*} T(n)&=\Theta(1)+\sum_{d=1}^{n-1}(\Theta(n-d) + \Theta(1) + \Theta(1))\\ &=\Theta(1)+2(n-1)\Theta(1)+\sum_{d=1}^{n-1} \Theta(n-d)\\ &=\Theta(n)+\sum_{k=1}^{n-1} \Theta(k)\\ &=\Theta(n)+\Theta\left(\frac{n(n-1)}{2}\right)\\ &=\Theta(n^2) \end{align*}

Le tri par propagation (tri à bulles)

Présentation de l'algorithme

Le principe du tri par propagation, généralement connu comme le tri à bulles est simple lui aussi. La mé­ta­pho­re est que le début de la liste symbolise le fond de l'eau et la fin de la liste la surface. Chaque nom­bre représente le diamètre d'une bulle et la bulle la plus grosse est celle qui remonte le plus vite à la surface (ce qui est conforme à la réalité physique dans une certaine mesure). Plus formellement, on parcourt la liste de la gauche vers la droite en échan­geant les termes contigus \(L[i]\) et \(L[i+1]\) s'ils sont mal rangés, c'est-à-dire si \(L[i+1] < L[i]\) (on propage la bulle \(L[i]\)). À ce stade, la bulle la plus grosse (la plus grande valeur) est au bout de la liste en position n.

À l'issu d'un passage sur la liste \(L\), on a l'assertion \(L[n]=\max L\).
Prouvez le lemme et écrivez un algorithme Propager\(\;(L,g,d)\) qui réalise la propagation des bulles dans la sous-liste \(L[g:d]\) où \((g,d)\in\ab{1}{\#L}^2\) et \(g\leq d\). Prouvez la validité de cet algorithme en montrant d'une part qu'il s'arrête et d'autre part que la propriété \(L[i]=\max L[g:i]\) est un invariant de votre boucle quand \(i\) désigne l'indice de la cellule de \(L\) qui est comparée à la suivante.

Le terme le plus grand étant à présent placé au bout de la liste, il suffit de recommencer le processus de propagation, mais cette fois sur la sous-liste \(L[1:n-1]\) con­te­nant les \(n-1\) premiers termes de la liste et ainsi de suite en éliminant le dernier terme de la liste à chaque passe. L'algorithme est constitué d'une boucle principale (ligne #8) qui fait varier la taille de l'intervalle \(\ab{1}{d}\) à parcourir dans la liste \(L\) en commençant par la liste entière avec \(d:=\#L\) en appelant à chaque étape l'algorithme de propagation. 

TriBulles(@L)
données
   L: liste de valeurs
variables
   d: entier
debut
   d ← #L
   TQ (d > 1) FAIRE
      Propager(L,1,d)	    
      d ← d - 1
   FTQ
FIN

On peut améliorer immédiatement cet algorithme en remarquant que si aucun échange n'a lieu lors d'une passe sur la liste, c'est qu'elle est triée et qu'il est alors inutile de balayer la liste à nouveau.

Si aucun échange n'a eu lieu lors d'une passe sur la liste par l'algorithme Propager alors la liste est triée.
Démontrez le lemme et modifiez l'algorithme Propager pour qu'il renvoie un booléen in­di­quant s'il y a eu ou non un ou plusieurs échange(s) lors du parcours de la liste.

L'algorithme peut alors exploiter cette optimisation à l'aide de la variable booléenne continuer ini­tia­li­sée à VRAI au départ et mise à jour par l'algorithme Propager. 

TriBulles(@L)
données
   L: liste de valeurs
variables
   d: entier
   EX: booléen
debut
   EX ← VRAI
   d ← #L
   TQ (EX ET (d > 1)) FAIRE
      EX ← Propager(L,1,d)
      d ← d - 1
   FTQ
FIN

Prouvons la validité de cet algorithme en oubliant pour le moment la version optimisée. La variable \(d\) est ini­tia­li­sée à la tail­le de la liste et n'est modifiée que par une décrémentation dans la boucle prin­ci­pa­le, la condition \(d > 1\) sera donc nécessairement fausse pour la valeur \(d=1\) si la boucle interne est valide et ne modifie pas la variable \(d\), ce qui est le cas (cf. exercice). Ainsi, l'algorithme s'arrête. La propriété \(L[d:n]\) est triée est un invariant de la boucle, en effet elle est vraie en entrant la pre­miè­re fois dans la boucle pour \(d=n\) puisqu'elle est réduite à un seul terme et nous savons que l'algorithme Propager place le plus grand élément de la liste \(L[1:d]\) à la position \(d\) ce qui ne modifie pas l'ordre de la liste \(L[d:n]\). Dans la version optimisée, nous savons déjà que l'algorithme s'arrête, il reste à s'assurer qu'il est toujours valide. La seule modification entre les deux versions est que l'algorithme peut sortir de la boucle avant que \(d\) ne soit égal à 1, i.e. quand la variable continuer est fausse, mais dans ce cas cela suppose que la liste est triée d'après le lemme précédent.

La table ci-dessous montre l'évolution de la liste pendant l'exécution de l'algorithme TriBulles. À chaque étape, les deux termes comparés sont matérialisés sur un fond rouge ou fond vert selon que leurs indices constituent une inversion et qu'il faut les échanger ou non. Le terme d'indice \(i\) est encadré. Vous pouvez saisir vos propres valeurs dans la liste \(L=[\)\(]\) pour étudier le processus à l'aide de la trace de l'exécution ci-dessous :

Démontrez le lemme 3.
Dans l'algorithme TriBulles, quelle modification mineure et sans impact sur sa validité pourrait néanmoins compromettre sa stabilité  ?

Complexité du tri à bulles

Dans sa version initiale, sans optimisation, la complexité du tri à bulle ne dépend que de la taille de l'instance, le \(i\)-ème passage sur la liste réalise exactement \(n-i\) comparaisons entre les termes contigus d'indices \(j\) et \(j+1\) pour \(j\in\ab{i}{n-1}\), autrement dit, il y a \begin{equation} \label{eq:sumcompbulle} \sum_{i=1}^{n-1}{\color{orange}\sum_{j=i}^{n-1}1}=\sum_{i=1}^{n-1}{\color{orange}(n-i+1)}=\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2} \end{equation} comparaisons et finalement \(T(n)=\frac{n(n-1)}{2}=\Theta(n^2)\).

Dans sa version optimisée, le nombre de comparaisons dépend également de la nature de l'instance. Dans le meilleur des cas, la liste est triée et le premier passage suffit à achever la pro­cé­du­re puisque la variable continuer reste fausse, aucun échange n'ayant eu lieu. On a donc réalisé exactement \(n-1\) comparaisons entre termes contigus de la liste :

\[\check T(n)=n-1=\Theta(n).\]

Dans le pire des cas, les valeurs sont triées dans l'ordre inverse et il y a sys­té­ma­ti­que­ment une trans­po­si­tion après chaque comparaison entre deux termes contigus. On retrouve le même calcul qu'en \((\ref{eq:sumcompbulle})\), soit exactement \(\frac{n(n-1)}{2}\) comparaisons : \[\hat T(n)=\Theta(n^2).\]

Le nombre moyen de comparaisons est très difficile à ob­te­nir. Il est tentant d'estimer la complexité d'un algorithme de tri à travers le nombre de transpositions (échanges) nécessaires pour réordonner les termes de la liste \(L\). C'est probablement l'analogie avec le coût physique d'une transposition — intervertir deux cartes dans une main par exemple —, qui est plus important qu'une simple comparaison (contrôle visuel) qui nous le suggère. Le fonctionnement du tri à bulles optimisé permet de se convaincre que ce serait une erreur. En effet, dans le cas où la liste est déjà triée, aucune transposition n'est effectuée et il aura pourtant fallu balayer l'intégralité des \(n\) termes de la liste pour s'en assurer, le coût est donc bien linéaire. Cependant, on peut exploiter le nombre moyen de transpositions pour minorer le nombre moyen de comparaisons, puisqu'une transposition n'est réalisée qu'après une comparaison, il y a au moins autant de comparaisons qu'il y a de trans­po­si­tions.

Rappelons que les listes considérées sont des permutations du groupe symétrique \(S_n\). Estimons le nombre de transpositions moyens nécessaires pour trier une liste/permutation. D'après le lemme, chaque échange entre termes contigus de la liste diminuant le nombre d'inversions de la liste d'une unité, le nombre total d'inversions des \(n!\) lis­tes/­per­mu­ta­tions de taille \(n\) est égal au nombre d'échanges total nécessaires à trier ces listes. Le résultat est fourni par ce résultat de combinatoire : \[\sum_{L\in S_n}\#{\mathscr I}(L)=n!\ \frac{n(n-1)}{4}.\] Il suffit de diviser par \(n!\), pour obtenir une minoration du nombre de comparaisons moyen du tri à bulles : \[\overline{T}(n)=\Omega\left(\frac{n(n-1)}{4}\right)=\Omega(n^2).\]

Le tri par insertion

Présentation de l'algorithme

Le tri par insertion est le plus difficile des trois. C'est celui que nous utilisons quand nous jouons aux cartes, plus précisément pendant la phase où l'on range ses cartes dans l'ordre croissant dans sa main. Chaque nouvelle carte est insérée à la bonne position par rapport aux cartes déjà rangées. L'insertion se fait en comparant la nouvelle carte avec celles déjà en main de la gauche vers la droite (ou le contraire) jusqu'à ce que la bonne position soit trouvée.

Il faut néanmoins adapter ce que nous faisons physiquement avec les modèles de données que nous manipulons et respecter les contraintes fixées. Nous voulons réaliser le tri in situ, on ne dispose donc que de la liste d'origine \(L\) et d'un nombre de variables indépendant de sa taille \(n\). Il faut donc imaginer que l'on va devoir ranger la \(i\)-ème carte \(L[i]\) dans la sous-liste \(L[1:i-1]\) qui est donc supposée triée (on rappelle que l'intervalle entier \([a:b]\) contient toutes les valeurs entre \(a\) et \(b\) incluses contrairement au Python qui exclut \(b\)).

L'insertion d'une carte \(L[i]\) dans la main/liste \(L[1:i-1]\) se fait indifféremment en parcourant les cartes dans la main de la gauche vers la droite ou de la droite vers la gauche. L'exercice suivant précise pourquoi il est préférable de faire la comparaison de la droite vers la gauche.

Notons \(j\) la position où la carte \(L[i]\) doit être insérée. Pour insérer la carte, ce qui se traduit algorithmiquement par l'instruction \(L[j]\leftarrow L[i]\), il faut au préalable décaler toutes les valeurs \(L[j]\) pour une variable \(k\) allant de \(j\) à \(i-1\) d'une position vers la droite afin de libérer la position \(j\), sans quoi la valeur \(L[j]\) serait perdue. Montrez que si ces décalages sont réalisés dans l'ordre croissant des indices \(k\in[j:i-1]\), alors toutes les valeurs de la sous-liste \(L[j:i]\) seront égales à \(L[j]\).

L'exercice met en lumière une erreur extrêmement courante, il est donc nécessaire de réaliser les dé­ca­la­ges \(L[k+1]\leftarrow L[k]\) en commençant par \(k=i-1\) et finir avec \(k=j\). Mais plutôt que de réaliser les décalages et ensuite insérer la carte à la position \(k\), on peut ramener la carte à la bonne position en l'échangeant avec les cartes de la main de la même manière que pour l'algorithme du tri par propagation mais en propageant la bulle de la droite vers la gauche. 

Inserer(L,i)
DONNÉES
   L: liste de valeurs
DEBUT
    TQ ((i > 1) ET (L[i] < L[i - 1])) FAIRE
        Echanger(L,i,i - 1)
        i ← i - 1
    FTQ
FIN

Comme pour le tri à bulle, on arrête la propagation dès que la carte/bulle est bien placée. Il suffit alors d'insérer toutes les cartes dans la main de la deuxième carte (la première l'est déjà) jusqu'à la dernière carte pour réaliser ce tri. 

TriInsertion(@L)
données
   L: liste de valeurs
variables
   i: entier
debut
    i ← 2
    TQ (i ≤ #L) FAIRE
       Inserer(L,i)
       i ← i + 1
    FTQ
FIN

La trace de l'exécution du TriInsertion pour la liste \(L=[\)\(]\) ci-dessous permet de comprendre le processus. Chaque ligne de la table représente une étape de l'insertion de la carte. Si la carte elle est à la bonne position elle est sur fond clair et si elle doit être déplacée, elle est sur fond fond rouge, la zone qui a été balayée pour l'insertion de la carte reste sur fond clair. Les différents échanges \(\leftrightarrows\) réalisés entre \(L[j]\) et \(L[j-1]\) sont spécifiés dans la dernière colonne.

Dans l'algorithme TriInsertion, quelle modification mineure et sans impact sur sa validité pourrait néanmoins compromettre sa stabilité  ?

Complexité du tri par insertion

Comme toujours avec les tris comparatifs, nous allons évaluer la complexité en estimant le nombre de comparaisons effectuées et ici pour ne pas compliquer inutilement l'exposé, nous ne compterons que celles entre les valeurs dans la liste. Dans le meilleur des cas, les cartes arrivent triées dans l'ordre croissant, la carte à insérer n'est comparée qu'une seule fois avec la carte la plus à droite dans la main et ne nécessite aucun décalage des cartes déjà placées. Il y a au total \(n-1\) comparaisons (il n'y a rien à comparer pour la première carte), la complexité dans le meilleur des cas est donc

\[\check T(n)=n-1=\Theta(n).\]

Dans le pire des cas, le calcul est tout aussi simple, on reçoit les cartes dans l'ordre décroissant et il faut donc décaler toutes les cartes déjà en main. L'insertion de la \(i\)-ème carte nécessite \(i-1\) com­pa­rai­sons, on retrouve donc très classiquement la somme des \(n-1\) premiers entiers soit \(\frac{n(n-1)}{2}\) :

\[\hat T(n)=\frac{n(n-1)}{2}=\Theta(n^2).\]

Pour le cas moyen, nous supposons encore que la liste \(L\) est une permutation de \(S_n\). Nous allons reprendre le corollaire de la première section pour évaluer la complexité moy­en­ne. À la différence du tri à bulles, le nombre de comparaisons est ici directement lié aux nombre d'échanges de valeurs contiguës. À chaque insertion d'une nouvelle carte, il y a exactement une comparaison de plus que d'échanges effectués.

Quand on insère la \(i\)-ème carte, les \(i-1\) premières sont supposées triées. Ainsi, si l'on tient compte de la comparaison qui termine la boucle, le nombre total de comparaisons \(c_i\) réalisées pour cette insertion est donné par \begin{equation}\label{eq:nbinv} c_i:=1+{\#\big\{j\in\ab{1}{i-1}\ \mid\ L[j]>L[i]\big\}}. \end{equation}

Notons \(c_L\) le nombre total de comparaisons réalisées pour trier la liste \(L\). Si l'on ne tient pas compte de l'élé­men­tai­re op­ti­mi­sa­tion de l'algorithme qui consiste à commencer par l'insertion de la deu­xième carte, on a \begin{align*} c_L&=\sum_{i=1}^{n}c_i\\ &=\sum_{i=1}^{n}\left(1+{\#\big\{(i,j)\ \such\ (j < i)\ \wedge\ (L[j]>L[i])\big\}}\right)\\ &=n+\#\big\{(i,j)\in\ab{1}{n}^2\ \such\ (j < i)\ \wedge\ (L[j]>L[i])\big\}\\ &=n+{\color{#FF0}\#{\mathscr I}(L)}. \end{align*}

Il suffit à présent de calculer la moyenne du nombre de comparaisons pour toutes les permutations du groupe symétrique \({S}_n\) : \begin{align*} \bar T(n) &=\frac{1}{n!}\sum_{L\in{S}_n}c_L\\ &=\frac{1}{n!}\sum_{L\in{S}_n}(n+\#{\mathscr I}(L))\\ &=n+\frac{1}{n!}{\color{orange}\sum_{L\in{S}_n}\#{\mathscr I}(L)}\\ \end{align*} Or le nombre d'inversions total pour toutes les permutations du groupe \({S}_n\) est égal à \(\color{orange}n!\ \frac{n(n-1)}{4}\), donc \begin{align*} \bar T(n)&=n+\frac{n(n-1)}{4}\\ &=\Theta(n^2). \end{align*}

Notons que la constante cachée est ici égale à \(\frac{1}{4}\), ce tri est donc censé être en moyenne deux fois plus rapide que tri par sélection dont la constante cachée est \(\frac{1}{2}\) (idem pour le tri à bulles, même si n'avons pas pu l'établir).

Écrivez un algorithme IdxMin\(\;(L,g,d)\) qui renvoie le plus petit indice d'un minimum de la sous-liste \(L[g\!:\!d]\) (on suppose que l'intervalle est celui des mathématiques et contient donc \(d\)).

Travaux pratiques

Toutes les fonctions et programmes sont à écrire en langage \(C\). L'objectif de ce tp est de comparer la complexité moyenne des trois tris empiriques. Les tris opéreront sur des permutations du groupe \({S}_n\), i.e. des tableaux \(T\) de taille \(n\) contenant chacun des \(n\) premiers entiers et renverront le nombre de comparaisons effectuées pour réaliser le tri. Remarque récurrente : la notation \([a:b]\), qui désignent les indices d'une sous-liste, contiennent les valeurs \(a\) et \(b\), contrairement au Python.

Écrivez une fonction uint *GenPerm(uint n) qui renvoie une permutation aléatoire de \(\mathfrak S_n\), au sens où sa probabilité est la probabilité uniforme \(1/(n!)\).

Indication : partir de la permutation identité \(S=[1,2,3,\ldots,n]\) puis, pour toutes les valeurs de \(i\) allant de \(1\) à \(n-1\), transposer (échanger) le \(i\)-ème terme avec le \(j\)-ème terme où la valeur de \(j\) est choisie au hasard dans l'intervalle fermé \(\ab{i}{n}\) (donc \(i\) et \(n\) sont inclus).

(1) Écrivez la fonction uint IdxMin(int *T, uint a, uint b) qui renvoie le plus petit indice de la valeur la plus petite du sous-tableau \(T[a:b]\), on suppose que \(0\leq a \leq b \leq \#T-1.\)

(2) Écrivez la fonction ullong TriSelection(int *T, uint n) qui reçoit en entrée un tableau \(T\) de \(n\) entiers et qui trie ce tableau à l'aide de l'algorithme du tri par sélection en vous appuyant sur la fonction IdxMin. La fonction renvoie le nombre de comparaisons réalisées.

(1) Écrivez la fonction ullong Propager(int *T, uint a, uint b, ullong *nbcomp) qui réalise la propagation des valeurs du sous-tableau \(T[a:b]\) en supposant que \(0\leq a,b < |T|\). Le parcours du sous-tableau se fera de gauche à droite si \(a < b\) et de droite à gauche si \(a > b\). La fonction renvoie le nombre d'échanges effectués. Le nombre de comparaisons réalisées est renvoyé via la variable *nbcomp.

(2) Écrivez la fonction ullong TriBulles(int *T, uint n, ullong *nbcomp) qui reçoit en entrée un tableau T de n  entiers et qui trie cette liste à l'aide de l'algorithme du tri à bulles. La fonction renvoie le nombre d'échanges effectués. Le nombre de comparaisons réalisées est renvoyé via la variable *nbcomp.

(3) Écrivez la fonction ullong TriCocktail(int *T, uint n, ullong *nbcomp) qui reçoit en entrée un tableau T de n  entiers et qui trie cette liste à l'aide de l'algorithme du tri cocktail : même principe que le tri par propagation, mais on propage alternativement de gauche à droite et de droite à gauche. La fonction renvoie le nombre d'échanges effectués. Le nombre de comparaisons réalisées est renvoyé via la variable *nbcomp.

(4) Comparez le nombre de comparaisons et le nombre d'échanges réalisés par le tri par propagation et le tri cocktail pour un même tableau à trier.

(5) Implantez l'algorithme du tri à peigne étudié en travaux dirigés sous la forme d'une fonction ullong TriPeigne(int *T, uint n, float coef, ullong *nbcomp). La fonction renvoie le nombre d'échanges effectués. Le nombre de comparaisons réalisées est renvoyé via la variable *nbcomp.

(6) Comparez les performances du tri peigne en fonction du coefficient de réduction coef. Vous testerez avec les coefficients suivants : \(1.1\) à \(2.0\) par pas de \(0.1\).

Écrivez une fonction ullong TriInsertion(int *T, uint n) qui reçoit en entrée un tableau \(T\) de \(n\) entiers et qui trie ce tableau à l'aide de l'algorithme du tri par insertion. La fonction renvoie le nombre de comparaisons réalisées.

On veut à présent comparer la complexité moyenne (en nombre de comparaisons) des tris sélection, propagation, insertion, peigne. Il faudrait calculer la somme des nombres de comparaisons pour chacune des permutations possibles mais la croissance de la fonction \(n\,!\) ne le permet pas. Calculez empiriquement le nombre \(K\) de permutations de taille \(n\) que vous pouvez trier en temps raisonnable (maximum 1 minute) pour chacun des tris. Estimez la complexité moyenne en tirant \(K\) permutations \(T\) de taille \(n\) au hasard parmi les \(n!\) permutations possibles (cf. sujet 1). Chaque permutation tirée au hasard sera triée par chacun des quatre algorithmes.

Tracez la courbe de complexité moyenne des quatre tris avec Gnuplot.

Démontrez que l'algorithme GenPerm suggéré dans le sujet plus haut pour créer une permutation aléatoire de \(n\) termes assure effectivement que la distribution de probabilités est bien la distribution uniforme où chaque évènement élémentaire a une probabilité de \(1/n!\). Indication : remarquer que l'entier à la position \(i\) a été tiré au hasard parmi les \(n-i+1\) valeurs à partir de sa position (lui compris).
Soit \(a\) et \(b\) deux entiers naturels tels que \(a\leq b\). On suppose que le tirage aléatoire d'une valeur dans l'intervalle \(\ab{a}{b}\) de \(\mathbb N\) est uniforme, i.e. de probabilité \(\frac{1}{b-a+1}\). Alors après le premier tirage dans l'intervalle \(\ab{1}{n}\), chaque valeur à la même probabilité \(\frac{1}{n}\) d'être choisie. Plus généralement, la \(i\)-ème valeur est choisie parmi les \(n-i+1\) valeurs restantes avec la probabilité \(\frac{1}{n-i+1}\) et ce choix est indépendant des précédents. La probabilité de choisir une permutation particulière est donc \[\prod_{i=1}^{n-1}\frac{1}{n-i+1}=\frac{1}{n\,!}\]