3. Tri par sélection
C'est une version volontairement inefficace de la catégorie des tris par sélection, l'amélioration est apportée dans un autre feuillet de cours.
3.1. Spécification abstraite
La liste (a1, a2, ... , an) est décomposée en deux parties : une partie triée (a1, a2, ... , ak) et une partie non-triée (ak+1, ak+2, ... , an); l'élément ak+1 est appelé élément frontière (c'est le premier élément non trié).
Le principe est de parcourir la partie non-triée de la liste (ak+1, ak+2, ... , an) en cherchant l'élément minimum, puis en l'échangeant avec l'élément frontière ak+1, puis à déplacer la frontière d'une position. Il s'agit d'une récurrence sur les minima successifs. On suppose que l'ordre s'écrit de gauche à droite (à gauche le plus petit élément, à droite le plus grand élément).
On recommence l'opération avec la nouvelle sous-suite (ak+2, ... , an) , et ainsi de suite jusqu'à ce que la dernière soit vide.
3.2. Spécification concrète
La suite (a1, a2, ... , an) est rangée dans un tableau T[...] en mémoire centrale. Le tableau contient une partie triée (en violet à gauche) et une partie non triée (en blanc à droite). On recopie le minimum de la partie non-triée du tableau dans la cellule frontière (le premier élément de cette partie).
si ak+1 > ap alors ak+1 <--- ap Fsi
et l'on obtient ainsi à la fin de l'examen de la sous-liste (ak+1, ak+2, ... , an) la valeur min(ak+1, ak+2, ... , an) stockée dans la cellule ak+1. La sous-suite (a1, a2, ... , ak, ak+1) est maintenant triée et l'on recommence la boucle de recherche du minimum sur la nouvelle sous-liste (ak+2, ak+3, ... , an) etc...
Tant que la partie non triée n'est pas vide, on range le minimum de la partie non-triée dans l’élément frontière.
3.3. Algorithme
Une version maladroite de l'algorithme mais exacte a été fournie par un groupe d'étudiants elle est dénommée /version 1/. Elle échange physiquement et systématiquement l'élément frontière Tab[i] avec un élément Tab[j] dont la valeur est plus petite (la suite (a1, a2, ... , ai) est triée) :
|
Algorithme Tri_Selection /Version 1/ début |
Voici une version correcte et améliorée du précédent (nous allons voir avec la notion de complexité comment appuyer cette intuition d'amélioration), dans laquelle l'on sort l'échange ai et aj de la boucle interne "pour j de i+1 jusquà n faire" pour le déporter à la fin de cette boucle.
Au lieu de travailler sur les contenus des cellules de la table, nous travaillons sur les indices, ainsi lorsque aj est plus petit que ai nous mémorisons l'indice "j" du minimum dans une variable " m ß j ; " plutôt que le minimum lui-même. A la fin de la boucle interne "pour j de i+1 jusquà n faire" la variable m contient l'indice de min(ai+1, ak+2, ... , an) et l'on permute l'élément concerné (d'indice m) avec l'élément frontière ai :
|
début |
3.4. Complexité
Choisissons comme opération élémentaire la comparaison de deux cellules du tableau. |
Pour les deux versions 1 et 2 :
Le nombre de comparaisons "si Tab[ j ] < Tab[ m ] alors" est une valeur qui ne dépend que de la longueur n de la liste (n est le nombre d'éléments du tableau), ce nombre est égal au nombre de fois que les itérations s'exécutent, le comptage montre que la boucle "pour i de 1 jusquà n-1 faire" s'exécute n-1 fois (donc une somme de n-1 termes) et qu'à chaque fois la boucle "pour j de i+1 jusquà n faire" exécute (n-(i+1)+1 fois la comparaison "si Tab[ j ] < Tab[ m ] alors".
La complexité en nombre de comparaison est égale à la somme des n-1 termes suivants (i = 1, ...i = n-1)
C = (n-2)+1 + (n-3)+1 +.....+1+0 = (n-1)+(n-2)+...+1 = n.(n-1)/2 (c'est la somme des n-1 premiers entiers).
La complexité en nombre de comparaison est de de l'ordre de n², que l'on écrit O(n²).
Choisissons maintenant comme opération élémentaire l'échange de deux cellules du tableau. |
Calculons par dénombrement du nombre d'échanges dans le pire des cas (complexité au pire = majorant du nombre d'échanges). Le cas le plus mauvais est celui où le tableau est déjà classé mais dans l'ordre inverse.
Pour la version 1
|
Au pire chaque cellule doit être échangée, dans cette éventualité il y a donc autant d'échanges que de tests. La complexité au pire en nombre d'échanges de la version 1 est de l'ordre de n², que l'on écrit O(n²). |
Pour la version 2
|
L'échange a lieu systématiquement dans la boucle principale "pour i de 1 jusquà n-1 faire" qui s'exécute n-1 fois : La complexité en nombre d'échanges de cellules de la version 2 est de l'ordre de n, que l'on écrit O(n). Un échange valant 3 transferts (affectation) la complexité en transfert est O(3n) = O(n) |
Toutefois cette complexité en nombre d'échanges de cellules n'apparaît pas comme significative du tri, outre le nombre de comparaison, c'est le nombre d'affectations d'indice qui représente une opération fondamentale et là les deux versions ont exactement la même complexité O(n²).
Exemple : soit la liste à 6 éléments ( 5 , 4 , 2 , 3 , 7 ,1 ), appliquons la version 2 du tri par sélection sur cette liste d'entiers. Visualisons les différents états de la liste pour la première itération externe contrôlée par i (i = 1) et pour les itérations internes contôlées par l'indice j (de j = 2 ... à ... j = 6) :
|
|
|
|
|
|
|
|
L'algorithme ayant terminé l'échange de T[1] et de T[6], il passe à l'itération externe suivante ( i = 2) :
etc....