Informatique


Tris et recherches

Aller à


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:
481725934

Etape 1: on permute les valeur 48 et 9
917254834

Etape 2: le 17 est déjà placé, on ne change rien
917254834

Etape 3: le 25 est déjà placé, on ne change rien
917254834

Etape 4: on permute les valeurs 34 et 48
917253448

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:
481725934
Etape 1: 48 est supérieur à 17, on permute
174825934
Etape 2: 48 est supérieur à 25, on permute
172548934
Etape 3: 48 est supérieur à 9, on permute
172594834
Etape 4: 48 est supérieur à 34, on permute
172593448

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:
172593448
Passe 2:
179253448
Passe 3:
917253448

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:

481725934

Etape 1:

481725934    4825934  174825934
17 en travail  Décalage de 48  17 à la nouvelle position

Etape 2:

174825934  17  48934  172548934
25 en travail  Décalage de 48  25 à la nouvelle position

Etape 3:

172548934    17254834  917254834
9 en travail  Décalage de 17, 25, 48  9 à la nouvelle position

Etape 4:

917254834  91725  48  917253448
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:
8469713205

Etape 1: tableau[0] et tableau[4] sont comparées et éventuellement permutées:

74698 13205

Etape 2: tableau[1] et tableau[5] sont comparées et éventuellement permutées:

71698 43205

Etape 3: tableau[2] et tableau[6] sont comparées et éventuellement permutées:

71398 46205

Etape 4: tableau[3] et tableau[7] sont comparées et éventuellement permutées:

71328 46905

Etape 5: tableau[4] et tableau[8] sont comparées et éventuellement permutées:

71320 46985
... 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:
Valeur2791011 1417182022
Indice01234 56789

Recherchons la valeur 20 dans le tableau.


Etape 1: on calcule IM

Valeur2791011 1417182022
Indice01234 56789
---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

Valeur2791011 1417182022
Indice01234 56789
--- 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

Valeur2791011 1417182022
Indice01234 56789
---  ID,IMIF

Etape 4: on compare la valeur 20 avec celle de l'indice IM. Elle sont égales, la recherche est terminée.