Le tri par sélection
Il est très simple: il consiste à sélectionner dans le tableau la plus petite valeur et de la permuter avec le premier élément du tableau, puis
la deuxième plus petite valeur (hors premier élément) et de la permuter avec le deuxième élément du tableu et ainsi de suite.
Par exemple:
Etape 1: on permute les valeur 48 et 9
Etape 2: le 17 est déjà placé, on ne change rien
Etape 3: le 25 est déjà placé, on ne change rien
Etape 4: on permute les valeurs 34 et 48
Le tri à bulles
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 un ordre croissant il faut que chaque valeur du tableau soit plus petite que celle qui suit (sauf pour le dernier élément!).
Par exemple:
Etape 1: 48 est supérieur à 17, on permute
Etape 2: 48 est supérieur à 25, on permute
Etape 3: 48 est supérieur à 9, on permute
Etape 4: 48 est supérieur à 34, on permute
Après le premier passage la valeur la plus grande est correctement positionnée, pour trier le tableau complètement il faut répéter plusieurs passages en vérifiant
qu'au moins une permutation ait lieu.
Lorsque plus aucune permutation n'apparaît le tableau est trié.
Passe 1:
Passe 2:
Passe 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 de travail
- 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 le contenu de la variable de travail à la nouvelle position laissé libre par le décalage
Par exemple:
Etape 1:
48 | 17 | 25 | 9 | 34 | |
| 48 | 25 | 9 | 34 | |
17 | 48 | 25 | 9 | 34 |
17 en travail | |
Décalage de 48 | |
17 à la nouvelle position |
Etape 2:
17 | 48 | 25 | 9 | 34 | |
17 | | 48 | 9 | 34 | |
17 | 25 | 48 | 9 | 34 |
25 en travail | |
Décalage de 48 | |
25 à la nouvelle position |
Etape 3:
17 | 25 | 48 | 9 | 34 | |
| 17 | 25 | 48 | 34 | |
9 | 17 | 25 | 48 | 34 |
9 en travail | |
Décalage de 17, 25, 48 | |
9 à la nouvelle position |
Etape 4:
9 | 17 | 25 | 48 | 34 | |
9 | 17 | 25 | | 48 | |
9 | 17 | 25 | 34 | 48 |
34 en travail | |
Décalage de 48 | |
34 à la nouvelle position |
Le tri Shell
Il s'agit d'une variante du tri par insertion.
On ne réalise plus un décalage de un à un, on utilise le décalage sur un pas plus important.
Une fois les permutations de ce pas effectuées, le pas est réduit.
Quand le pas est égale à 1 on revient à un simple tri par insertion.
Remarque: le pas n'est pas calculé par hasard !
Par exemple, en utilisant un pas de 4:
Etape 1: tableau[0] et tableau[4] sont comparées et éventuellement permutées:
Etape 2: tableau[1] et tableau[5] sont comparées et éventuellement permutées:
Etape 3: tableau[2] et tableau[6] sont comparées et éventuellement permutées:
Etape 4: tableau[3] et tableau[7] sont comparées et éventuellement permutées:
Etape 5: tableau[4] et tableau[8] sont comparées et éventuellement permutées:
... et ainsi de suite...
La recherche dichotomique
Elle ne s'applique que sur les tableaux déjà triés.
La méthode consiste à calculer l'indice situé au milieu du tableau (IM), pour ce faire on prend la division entière de l'indice de fin (IF) plus
l'indice de début (ID), le tout divisé par 2.
On donc: IM = (IF + ID)/2
Exemple:
Valeur | 2 | 7 | 9 | 10 | 11 |
14 | 17 | 18 | 20 | 22 |
Indice | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
Recherchons la valeur 20 dans le tableau.
Etape 1: on calcule IM
Valeur | 2 | 7 | 9 | 10 | 11 |
14 | 17 | 18 | 20 | 22 |
Indice | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
--- | ID | | IM |
| IF |
Etape 2: on compare la valeur 20 avec celle de l'indice IM. Etant inférieur cela veut dire que la valeur 20 est forcément après l'indice 4.
On recalcule l'IM à partir de l'indice 5.
IM = (9 + 5)/2 = 7
Valeur | 2 | 7 | 9 | 10 | 11 |
14 | 17 | 18 | 20 | 22 |
Indice | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
--- | | ID |
| IM | | IF |
Etape 3: on compare la valeur 20 avec celle de l'indice IM. Etant inférieur cela veut dire que la valeur 20 est forcément après l'indice 7.
On recalcule l'IM à partir de l'indice 5.
IM = (8 + 9)/2 = 8
Valeur | 2 | 7 | 9 | 10 | 11 |
14 | 17 | 18 | 20 | 22 |
Indice | 0 | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 |
--- | |
ID,IM | IF |
Etape 4: on compare la valeur 20 avec celle de l'indice IM. Elle sont égales, la recherche est terminée.