Algorithmique ii - Analyse des tris empiriques

Généralités

Nous allons revisiter les trois algorithmes de tri empiriques étudié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 s'appuient 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 opé­ra­tions usuelles sur les listes. Ces questions seront abor­dées plus en détail dans le chapitre Listes, files, piles.

Outre le fait qu'ils peuvent opérent sur des tableaux, ces trois algorithmes partagent les ca­rac­té­ris­ti­ques sui­vantes :

  1. Ce sont des tris comparatifs, ils s'appuient sur des comparaisons des termes de la liste pour les trier (avec la relation d'ordre total \(\leq\) de l'ensemble sous-jacent) ;
  2. Ce sont des tris in situ. Autrement dit ils agissent directement sur la liste d'entrée et ne nécessitent qu'un nombre constant de va­riab­les auxiliaires (indépendant de la taille de la liste à trier).

En revanche seuls les tris par propagation et par insertion sont des tris stables, c'est-à-dire qu'il ne mo­difient pas la position relative des termes égaux entre-eux (si un terme \(x_1:=x\) est placé avant un autre terme \(x_2:=x\) dans la liste, et que l'algorithme modifie la position de l'un ou l'autre, \(x_1\) reste toujours placé avant \(x_2\).) Cette caractéristique peut s'avérer importante pour des listes de \(k\)-uplets que l'on peut trier suivant la composante de son choix, la clef de tri. Un tri stable permettra de trier successivement la liste selon des clés différentes sans perturber localement le classement obtenu par le tri selon une clef précédente. On peut par exemple trier une liste d'individus suivant leur taille puis la trier à nouveau suivant leur poids ; si le tri est stable les personnes de même poids restent rangées dans l'ordre de taille ce qui n'est pas nécessairement le cas avec un tri qui n'est pas stable.

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ésignerons par \(L[i\colon j]\) la sous-liste constituée des éléments de la liste \(L\) dont les indices sont dans l'intervalle \([i,j]\) (attention à la confusion possible 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 comparaisons 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 munie 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 complexité est constante \(T_{\leftrightarrows}(n)=\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:[1,n]\rightarrow [1,n]\) est une per­mu­ta­tion du groupe symétrique \({\frak S}_n\). L'algorithme Echanger réalise alors la transposition \((L[i],L[j])\) que nous noterons \(\tau_{L[i],L[j]}\) pour éviter que ce \(2\)-cycle ne soit confondu avec un couple.

Nous noterons \({\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\{(\sigma(i),\sigma(j))\in[1,n]^2\mid i < j\ \text{et}\ \sigma(i) > \sigma(j)\big\} \end{equation}

Le résultat suivant nous sera utile pour le tri à bulles et le tri par insertion, il affirme que si l'on échan­ge deux éléments consécutifs dans une liste pour les ranger dans l'ordre, on diminue ex­ac­te­ment le nombre d'in­ver­sions de 1.

Soit \(\sigma\in{\frak S}_n\) et \(k\in[1,n-1]\) tels que \((\sigma(k),\sigma(k+1))\in{\mathscr I}(\sigma).\) Alors \begin{equation} \#{\mathscr I}(\tau_{\sigma(k),\sigma(k+1)}\circ\sigma)=\#{\mathscr I}(\sigma)-1. \end{equation}
Considérons un couple \((i,j)\in[1,n]^2\) tel que \(i < j\) et notons \(\sigma':=\tau_{\sigma(k),\sigma(k+1)}\circ\sigma\). Étudions le statut (inversion ou non) de \((\sigma(i),\sigma(j))\) et de \((\sigma'(i),\sigma'(j))\), 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)\) dans la permutation \(\sigma\) : \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}\sigma(k+1)}&\cdots&\sigma(n-1)&\sigma(n)\\ \sigma':&\sigma(1)&\sigma(2)&\sigma(3)&\cdots& {\color{#F84}\sigma(k+1)}&{\color{#F84}\sigma(k)}&\cdots&\sigma(n-1)&\sigma(n) \end{matrix} \end{equation} Les seules différences de statut éventuelles entre \((\sigma(i),\sigma(j))\) et \((\sigma'(i),\sigma'(j))\) ne sont possibles que pour des indices \((i,j)\) tels que \(i\in\{k,k+1\}\) ou \(j\in\{k,k+1\}\) puisque pour tous les autres indices \(l\) on a \(\sigma(l)=\sigma'(l)\).

Dans le premier cas le couple \((\sigma(k),\sigma(k+1))\) qui était une inversion de \(\sigma\) n'est plus une inversion de la permutation \(\sigma'\) par construction. Les deux derniers cas étant symétriques, nous ne traiterons que le cas 2. Pour tout \(i\in[1,k[\), après la transposition \(\tau_{\sigma(k),\sigma(k+1)}\), le statut du couple \((\sigma'(i),\sigma'(k))\) est celui du couple \((\sigma(i),\sigma(k+1))\) et celui de \((\sigma'(i),\sigma'(k+1))\) est celui du couple \((\sigma(i),\sigma(k))\) ce qui ne change pas le nombre global d'inversions.

Dans la preuve du lemme, vérifiez que les 5 cas de figure (1, 2i, 2ii, 3i, 3ii) constituent bien une partition de l'ensemble des couples \((i,j)\in[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 \(\tau_{\sigma(i),\sigma(j)}\) de deux termes non-contigüs d'indices \(i\) et \(j\) constituant une in­ver­sion, la permutation \(\sigma'\) 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[g,d]\) tel que \[L[i_{\min}]=\min_{i\in[g,d]}\{L[i]\}.\]

D'après l'exercice précédent, on sait calculer une position \(i_{\text{min}}\) d'un minimum dans la liste \(L\), il suffit de l'échanger avec le premier élément de la liste, soit \(L[1] \leftrightarrows L[i_{\text{min}}]\) et de recommencer à partir de la deuxième position (on travaille sur la sous-liste \(L[2\colon 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 contigüs \(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 liste \(L[g\colon d]\) où \((g,d)\in[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\colon 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\colon 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 la zone \([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
   continuer: booléen
debut
   continuer ← VRAI
   d ← #L
   TQ (continuer) ET (d > 1) FAIRE
      continuer ← 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\colon 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\colon d]\) à la position \(d\) ce qui ne modifie pas l'ordre de la liste \(L[d\colon 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 le meilleur des cas, les valeurs sont déjà triées et le premier passage suffit à achever la pro­cé­du­re puisque la variable continuer reste fausse car aucun échange n'a eu lieu. On a donc réalisé \(n-1\) comparaisons entre les termes de la liste et

\[\check T(n)=\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 per­mu­ta­tion après chaque comparaison entre deux termes contigüs. La taille de la sous-liste à traiter décroit d'une unité à chaque nouveau passage, on retrouve la somme des \(n-1\) premiers entiers soit \[\hat T(n)=\Theta(n^2).\]

Notons que la constante cachée est \(\frac{1}{2}\). Le nombre moyen de comparaisons est très difficile à ob­te­nir dans la version présentée plus haut et qui arrête le processus de tri si aucun échange n'a eu lieu lors d'une passe. Sans cette optimisation, on retrouve exactement le même nombre de comparaisons que dans le pire des cas. En revanche, le nombre moyen d'échanges est exactement le même que pour le tri par insertion que nous allons étudier plus loin.

Il est tentant de vouloir estimer la complexité d'un algorithme de tri à travers le nombre de transpositions nécessaires pour ordonner les termes de la liste \(L\). C'est (probablement) l'analogie avec le coût physique d'une transposition (intervertir deux fiches par exemple) qui est plus important qu'une simple comparaison (contrôle visuel) qui nous le suggère. Le fonctionnement du tri à bulles 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 dispenser, le coût est donc bien linéaire et pas nul !

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 repecter 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\colon i-1]\) qui est donc supposée triée (on rappelle que l'intervalle entier \([a\colon 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\colon 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\colon i-1]\), alors toutes les valeurs de la sous-liste \(L[j\colon 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 le TriBulles mais en sens inverse.

TriInsertion(@L)
données
   L: liste de valeurs
variables
   i,j: entier
debut
    i ← 2
    TQ (i ≤ #L) FAIRE
       j ← i
       TQ (j > 1) ET (L[j - 1] > L[j]) FAIRE
          Echanger(L,j,j - 1)
          j ← j - 1
       FTQ
       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 les comparaisons entre valeurs de 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, la complexité dans le meilleur des cas est donc

\[\check T(n)=\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 \(n(n-1)/2\), soit une complexité de

\[\hat T(n)=\Theta(n^2).\]

Pour le cas moyen, nous allons supposer que la liste \(L\) des valeurs à trier est une permutation des \(n\) premiers entiers non-nuls, ce qui ne restreint pas la généralité comme nous le verrons dans le cha­pi­tre suivant. Le résultat suivant est un corollaire direct du lemme de la première section Nous allons exploiter cette information pour évaluer la complexité moyenne.

Le nombre d'échanges effectués par l'algorithme du tri par insertion pour trier la liste \(L\) est égal au nombre d'inversions \(\#{\mathscr I}(L)\).

Quand on insère la \(i\)-ème carte, rappelons que les \(i-1\) premières sont 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:={\#\big\{j\in[1,i-1]\ \mid\ L[j]>L[i]\big\}}+1. \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 la mi­cros­co­pi­que optimisation 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({\#\big\{(i,j)\ |\ j < i\ \text{et}\ L[j]>L[i]\big\}}+1\right)\\ &=n+\#\big\{(i,j)\in[1,n]^2\ \mid\ j < i\ \text{et}\ 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 \({\frak S}_n\) : \begin{align*} \bar T(n) &=\frac{1}{n!}\sum_{L\in{\frak S}_n}c_L\\ &=\frac{1}{(n-1)!}+\frac{1}{n!}\sum_{L\in{\frak S}_n}\#{\mathscr I}(L)\\ \end{align*} Or le nombre d'inversions total pour toutes les permutations du groupe \({\frak S}_n\) est égal à \(n!\ \frac{n(n-1)}{4}\), donc \begin{align*} \bar T(n)&=\frac{1}{(n-1)!}+\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 sensé être deux fois plus rapide que le tri à bulles ou le tri pas sélection dont la constante cachée est \(\frac{1}{2}\).

Travaux pratiques

Écrivez l'algorithme IdxMin\(\;(L,g,d)\) pour qu'il renvoie l'indice d'un minimum de la sous-liste \(L[g\!:\!d]\).

Écrivez la fonction IdxMin(L,a,b) qui renvoie le plus petit indice de la valeur la plus petite de la sous-liste \(L[a\colon b]\) (contrairement à Python, l'intervalle \([a\colon b]\) contient \(a\) et \(b\)), on suppose que \(1\leq a \leq b \leq \#L\). Écrivez la fonction TriSelection(L) qui reçoit en entrée une liste \(L\) de \(n\) entiers et qui trie cette liste à l'aide de l'algorithme du tri par sélection en vous appuyant sur la fonction IdxMin. Évaluez de manière empirique le nombre de comparaisons effectuées par l'algorithme dans le pire des cas en fonction du nombre de termes à trier.

Écrivez la fonction TriBulles(L) qui reçoit en entrée une liste L de entiers et qui trie cette liste à l'aide de l'algorithme du tri à bulles. Évaluez de manière empirique le nombre de comparaisons effectuées par l'algorithme dans le pire des cas en fonction du nombre de termes à trier.
Écrivez une fonction Python TriInsertion(L) qui reçoit en entrée une liste \(L\) de \(n\) entiers et qui trie ce tableau à l'aide de l'algorithme du tri par insertion. Évaluez de manière empirique le nombre de comparaisons effectuées par l'algorithme dans le pire des cas en fonction du nombre de termes à trier. Quelle est la nature du tableau qui correspond au meilleur des cas ? Faites de même pour l'analyse empirique.

Écrivez une fonction Python TrierTout(n) qui trie l'ensemble des \(n!\) permutations possibles de \({\frak S}_n\) et renvoie le nombre total de comparaisons réalisées divisé par \(n!\). Tracez la courbe avec \(n\) en abscisse et cette valeur en ordonnée pour \(n\in[1,10]\) avec Gnuplot.

Comparez le nombre de comparaisons moyen effectuées par ces trois algorithmes de tris en fonction de la taille de la liste \(n\) trier et tracez les trois courbes avec Gnuplot. La moyenne sera ici calculée de manière empirique en triant des listes de taille \(n\) fixée dont les termes auront été tirés aléatoirement. La taille maximale des listes et le nombre d'échantillons seront choisis pour respecter un temps de calcul de l'ordre de quelques minutes pour analyser chacun des algorithmes de tri. On supposera que les listes sont des permutations de \(\mathfrak S_n\).

Pour créer une permutation aléatoire de \(\mathfrak S_n\) (au sens où sa probabilité est la probabilité uniforme \(1/n!\)), partir de la permutation identité \((1,2,3,\ldots,n)\) puis transposer le \(i\)-ème terme avec l'un des termes suivants (donc de la position \(i\) à la position \(n\) incluses) choisi au hasard et ceci pour toutes les valeurs de \(i\) allant de \(1\) à \(n-1\).

Démontrez que l'algorithme suggéré dans le sujet de tp ci-dessus pour créer une permutation aléatoire assure effectivement que chaque permutation a une probabilité de \(1/n!\).