Procédé :
L'un des algorithmes de tri les plus simples procède de la manière suivante. On commence par rechercher l'élément de plus petite valeur du tableau pour l'échanger avec celui en première position, puis on recherche l'élément ayant la deuxième plus petite valeur pour l'échanger avec celui en deuxième position et l'on continue ainsi jusqu'à ce que le tableau soit entièrement trié.
Cette méthode porte le nom de tri par sélection car elle procède à la « sélection » successive de l'élément minimal parmi ceux restants.

Variable d'entrée et de sortie :
t est un tableau désordonné comportant n élément de type entier (dans notre exemple).
La variable de sortie est le tableau t trié.

Variables :
q est de même type que la variable t[i].
i, j et min sont des entiers. La variable i est utilisée comme variable d'incrémentation, et, j et min sont utilisées dans le processus d'inversion de place de deux éléments.

Algorithme :

Procédé :
Le tri par insertion est un algorithme presque aussi simple que le précédent mais peut-être plus souple. On considère les éléments les uns après les autres en insérant chacun à sa place parmi ceux déjà triés (et gardés comme tels). Pour insérer l'élément couramment considéré, on déplace simplement les éléments qui lui sont supérieurs un cran vers la droite et on l'insère dans la place laissée vacante.

Variable d'entrée et de sortie :
t est un tableau désordonné comportant n élément de type entier (dans notre exemple).
La variable de sortie est le tableau t trié.

Variables :
v est de même type que la variable t[i].
i, j sont des entiers. La variable i et j sont utilisées comme variable d'incrémentation.
La variable de sortie est le tableau t trié.

Algorithme :

Recette :
Problème dans le cas suivant :

Au premier passage, on a :

Problème :
La valeur t[0] n'a pas été défini. Une erreur de dépassement de capacité sera générée. Donc, pour que l'algorithme reste stable, on crée la variable t[0] en lui affectant la plus petite valeur, dans notre cas : t[0] = 0. On appelle t[0] sentinelle du tableau t, et elle se place toujours à gauche ou à droite de l'ensemble à trier.
En conclusion, les sentinelles ont pour but principale d'assurer la stabilité d'un algorithme de tri. Dans notre cas, la sentinelle avait pour valeur 0, la plus petite valeur de l'ensemble. L'utilisation d'une sentinelle impose comme contrainte de connaître ou de pouvoir estimer les bornes inférieures ou supérieures de l'ensemble à trier.

Nouvel algorithme :

Procédé :
On effectue autant de passes qu'il le faut en échangeant les éléments adjacents s'ils sont dans un mauvais ordre relatif ; lorsque aucun échange n'est plus nécessaire, le fichier est trié.

Variable d'entrée et de sortie :
t est un tableau désordonné comportant n élément de type entier (dans notre exemple).
La variable de sortie est le tableau t trié.

Variables :
v est de même type que la variable t[i].
i, j sont des entiers. La variable i et j sont utilisées comme variable d'incrémentation.
La variable de sortie est le tableau t trié.

Algorithme :

Recette :
De part le procédé de l'algorithme si aucun changement n'est fait dans la deuxième boucle le tableau est trié. Dans le cas suivant on peut arrêter les calculs plutôt :

Nouveau algorithme :
Le booléan s indique si la boucle s'arrête ou non.

Procédé :
Le tri par insertion doit sa lenteur au fait que les échanges ne portent que sur des éléments adjacents. Par exemple, si le plus petit élément est situé en fin de tableau, N étapes sont nécessaires pour le ramener à sa place définitive.
Le tri Shell est une généralisation simple et plus efficace du tri par insertion, car permettant l'échange d'éléments éventuellement très éloignés.
L'idée est de réorganiser le fichier de manière à obtenir un sous-fichier ordonné en sélectionnant tous les hième éléments (à partir de n'importe quelle position initiale). Un tel fichier est dit h-ordonné et il est constitué de h sous-fichiers ordonnés indépendants, entrelacés.
En h-ordonnant le fichier pour une grande valeur de h, on échange des éléments très distants dans le tableau, afin de faciliter la même opération pour les valeurs inférieures de h.
L'utilisation d'une telle méthode avec une série décroissante de h terminée par 1 résulte en un tableau trié : c'est le principe du tri Shell.

Une manière d'implanter le tri Shell serait d'utiliser, pour chaque valeur de h, un tri par insertion de manière indépendante, sur chacun des h fichiers. (Il ne serait pas question de recourir à des sentinelles à cause de leur nombre pour les plus grandes valeurs de h) On peut, en revanche, faire beaucoup mieux que cela : si l'on remplace chaque apparition de « 1 » par « h » (et de « 2 » par « h+l ») dans le tri par insertion.

Ce programme utilise la suite ..., 1093, 364, 121, 40, 13, 4, 1. D'autres suites d'incréments donnent d'aussi bons résultats en pratique mais il faut les choisir avec soin, comme nous allons le voir.

La suite d'incréments de ce programme est simple à engendrer et conduit à un tri efficace. D'autres suites conduisent à d'encore meilleurs résultats, mais il s'avère difficile d'obtenir un programme plus rapide de plus de 20% que le précédent, même pour des valeurs assez grandes de N. A l'inverse, il existe des suites très défavorables, comme ..., 64, 32, 16, 8, 4, 2, 1; celle-ci conduit à de mauvaises performances car les éléments aux Positions impaires ne sont comparés aux éléments en position paire qu'à la fin. De même, le tri Shell est parfois implanté en partant de h=N (au lieu de s'arranger pour toujours obtenir la même suite de valeurs comme dans le programme ci-contre). Ceci garantit virtuellement la rencontre d'une série défavorable pour un certain N.

Variable d'entrée et de sortie :
t est un tableau désordonné comportant n élément de type entier (dans notre exemple).
La variable de sortie est le tableau t trié.

Variables :
v est de même type que la variable t[i].
i, j sont des entiers. La variable i et j sont utilisées comme variable d'incrémentation.
h est un entier. h est le n-ième termes de la suite d'incrément.
La variable de sortie est le tableau t trié.
s est un booléan indiquant la fin de la boucle (Elle évite le dépassement d'indice dans le tableau t).

Algorithme :

Procédé :
Le procédé du tri rapide est de base très simple. Le tri des éléments s'organise autour d'un élément appelé pivot. L'algorithme compare tous les éléments aux pivots, il les range à droite si l'élément comparé est plus grand, et à gauche si il est plus petit. Le pivot se trouve alors rangé parmi les éléments. Puis de manière récursive, l'algorithme s'exécute sur les groupes d'éléments à gauche et droite du pivot.
Note :
Le pivot peut-être déterminé de façon différente, ici, on prendra le premier élément du groupe à trier.
Exemple :
On veut trier le groupe d'éléments : 5, 3, 9, 1, 8, 6, 4, 7
On obtient alors l'arborescence suivante :

Les nombres en gras sont les pivots pour chaque déroulement récursif de l'algorithme. Le traitement récursif s'arrête lorsqu'il y a un ou aucun élément dans le tableau, et, Chaque case de l'arborescence correspond à un appel de l'algorithme.

Variable d'entrée et de sortie :
t est un tableau désordonné comportant n élément de type entier (dans notre exemple).
La variable de sortie est le tableau t trié.

Variables :
p est le pivot, il est donc de même nature que les éléments du tableau t.
i, j sont des entiers utilisés comme variable d'incrémentation.
u sert au échange d'élément dans le tableau t, u est donc de même nature que les éléments du tableau t.
La variable Stop est de type booléenne, elle sert a arrêté la boucle.
La variable de sortie est le tableau t trié.

Module :
Les paramètres de la procédure TriRapide sont les suivant :
g et d sont les bornes respectivement inférieure et supérieure délimitant le sous-tableau à ranger.
t est le tableau des éléments à ranger.
s est un booléan indiquant la fin de la boucle (Elle évite le dépassement d'indice dans le tableau t).

Algorithme : Procédure TriRapide (g : Entier ; d : Entier ; var t : type de tableaux)


Remarques : Cette algorithme est rendu stable par deux sentinelles, une à droite du tableau avec la plus grande valeur du tableau à trier et une à gauche avec la plus petite valeur du tableau à trier.

Télécharger le code et l'éxécutable.

Tri.bas ( Afficher le code)