Les algorithmes des tris
a) Le principe
Nous avons vu l’intérêt des tableaux pour le stockage de valeurs multiples. Mais
suivant le cas il peut être utile d’avoir besoin d’obtenir une liste ordonnée de
valeurs par ordre croissant ou décroissant. Autrement dit vous voulez trier le
contenu du tableau. Prenez le cas d’un professeur souhaitant trier les notes de ses
étudiants de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour
le rendre plus lisible.
Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les
valeurs s’étalent entre 1 et 49. Voici l’état initial du tableau suite au tirage au sort :
Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles
ont toutes leurs qualités et leurs défauts. Ainsi une méthode sera lente, l’autre sera
plus gourmande en mémoire, et ainsi de suite. C’est leur complexité qui
détermine leur usage notamment pour de grandes plages de valeurs.
1) Le tri par création
2) Le tri par sélection
3) Le tri à bulles
4) Le tri par insertion
5) Le tri Shell
Le Tri par Création
Nous n’aborderons le tri par création que du point de vue théorique. En effet si
cette méthode semble simple, elle est en fait lourde et compliquée. Si on demande
à un débutant en programmation comment trier un tableau, il vous proposera très
certainement de créer un deuxième tableau dans lequel on placera au fur et à
mesure les éléments du premier tableau dans l’ordre croissant.
C’est une très mauvaise idée pour de multiples raisons dont :
L’ajout d’un second tableau double la mémoire nécessaire.
La recherche du plus petit élément est plus compliquée qu’on ne le pense car à
chaque passage, il ne faut pas reprendre ceux déjà sortis, et c’est compliqué.
Le nombre de boucles et de recherches est important. La complexité de
l’algorithme résultant aussi, supérieure aux autres.
Pour toutes ces raisons le tri par création ne doit absolument pas être
utilisé.
Le Tri par Sélection
Le tri par sélection consiste à sélectionner dans le tableau la plus petite valeur et la
permuter avec le premier élément du tableau, puis la deuxième plus petite valeur
(hors premier élément) et à la permuter avec le deuxième élément du tableau, et
ainsi de suite, et cela pour tous les éléments du tableau. Voici les étapes
nécessaires depuis l’exemple ci-dessus :
Étape 1 : la plus petite valeur est 9, on permute 9 et 48 .
Étape 2 : la plus petite valeur suivante est 17, déjà à la bonne position, on passe
à la suivante.
Le Tri par Sélection
Étape 3 : la plus petite valeur suivante est 25, déjà à la bonne position, on
passe à la suivante.
Étape 4 : la plus petite valeur suivante est 34, on permute 34 et 48. Le tableau est
trié.
Si le principe est simple, l’algorithme résultant nécessite malheureusement la
recherche dans tout ou partie du tableau de la plus petite valeur possible et ce
sans grande optimisation possible. On peut par contre éviter de permuter des
valeurs si aucune valeur inférieure n’a été trouvée. Voici l’algorithme :
Le Tri à Bulles
Le but du tri à bulles est que par permutations successives des valeurs voisines,
les valeurs les plus élevées remontent vers les dernières places du tableau,
tandis que les valeurs les plus basses migrent vers les premières places. Pour
trier dans un ordre croissant, il faut que chaque valeur d’un élément du
tableau soit plus petite que celle de l’élément qui suit (sauf pour le dernier,
bien entendu). L’état initial du tableau suite au tirage au sort étant :
Voici une simulation pas à pas du premier passage de l’algorithme de tri à bulles:
Étape 1 : 48 est supérieur à 17, on permute.
Le Tri à Bulles
Étape 2 : 48 est supérieur à 25, on permute.
Étape 3 : 48 est supérieur à 9, on permute.
Étape 4 : 48 est supérieur à 34, on permute.
À l’issue de ce premier passage, nous remarquons que la valeur la plus élevée
est déjà en dernière place du tableau mais que le tableau n’est pas entièrement
trié. Aussi il faut effectuer plusieurs passages en vérifiant à chaque passage si des
permutations ont eu lieu. Quand une permutation au moins a eu lieu lors d’un
passage, il faut en relancer une autre. Ainsi il faut mettre en place un drapeau (flag)
indiquant si une permutation a eu lieu ou non. Voici les résultats après les passages
successifs :
Le Tri à Bulles
À l’issue de ce premier passage, nous remarquons que la valeur la plus élevée est
déjà en dernière place du tableau mais que le tableau n’est pas entièrement trié.
Aussi il faut effectuer plusieurs passages en vérifiant à chaque passage si des
permutations ont eu lieu. Quand une permutation au moins a eu lieu lors d’un
passage, il faut en relancer une autre. Ainsi il faut mettre en place un drapeau (flag)
indiquant si une permutation a eu lieu ou non. Voici les résultats après les passages
successifs :
Passage 1:
Passage 2:
Passage 3:
Le tri par insertion
Le tri par insertion consiste à sélectionner un élément du tableau et à
l’insérer directement à la bonne position dans la partie du tableau déjà triée.
On procède en trois étapes :
On place l’élément à trier dans une variable temporaire.
Tant que les éléments du tableau qui précèdent l’élément à trier lui sont
supérieurs, on décale ces éléments d’une position en récupérant l’espace vide
laissé par l’élément à trier.
On insère ensuite la variable temporaire à la nouvelle position laissée vacante
par le décalage.
Voici les différentes étapes pour le tableau exemple :
Étape 1 : le deuxième élément 17 est placé dans une variable temporaire qui est
comparée aux éléments qui le précèdent. Chacun est décalé tant qu’il est
supérieur à l’élément à trier.
Étape 2 : 25 est comparé aux éléments qui le précédent et chacun est décalé
jusqu’à ce que l’élément ne soit plus supérieur au troisième.
Étape 3 : 9 est comparé aux éléments qui le précèdent. Ici comme dans
l’étape 1 on s’arrête forcément au premier élément.
Étape 4 : 34 est comparé aux éléments qui le précèdent. Seul 48 lui est
supérieur.
