Définitions
- Un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée.
- Un algorithme de tri est une suite finie d'instructions servant à réordonner une séquence d'éléments suivant un critère fixé à priori. Ce critère est en effet une relation d'ordre total sur les éléments à trier.
- La conception d'un algorithme de tri dépend du support matériel de la séquence de valeurs à trier (en mémoire centrale ou sur une mémoire secondaire) :
- Mémoires centrales : rapides (en nanosecondes) mais de taille limitée (en Mo).
- Mémoires secondaires : lentes (en microsecondes) mais de grande taille (en Go).
1. Tri par sélection
Principes :
- Trouver le plus petit élément et le mettre au début de la liste
- Trouver le 2ème plus petit et le mettre en seconde position
- Trouver le 3ème plus petit élément et le mettre à la 3ème place...
Autrement dit :
- Commencer par
i=1et on cherche la position de l'élément le plus petit du tableau (pos_min). - Une fois cet emplacement trouvé, on compare son contenu avec
T[1]et s'ils sont différents, on permute l'élément de l'emplacement trouvé par l'élément de la première positionT[1], sinonT[1]reste à sa place → Après ce parcours le premier élément est bien placé. - On recommence le même procédé pour le reste du tableau (
T[2]..T[n]). - Ainsi de suite jusqu'à la dernière partie du tableau (
T[n-1], T[n]).
En Algorithme :
procédure tri_selection(tableau t, entier n)
pour i de 1 à n - 1
min ← i
pour j de i + 1 à n
si t[j] < t[min], alors min ← j
fin pour
si min ≠ i, alors échanger t[i] et t[min]
fin pour
fin procédure
En Pascal :
procedure Tri_par_selection(n : integer ; var t : tab);
var i, j, min, tmp : integer;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
if (t[j] < t[min]) then min:=j;
if (i <> min) then
begin
tmp := t[i];
t[i] := t[min];
t[min] := tmp;
end; end; end;
2. Tri par insertion
Principes :
- Ordonner les deux premiers éléments
- Insérer le 3ème élément de manière à ce que les 3 premiers éléments soient triés
- Insérer le 4ème élément à “sa” place...
- Insérer le nème élément à sa place.
Autrement dit :
Faire remonter le plus grand élément du tableau en comparant les éléments successifs.
- On commence par
i=1, on compare le 1er (T[1]) et le 2éme élément (T[2]), s'ils ne sont pas dans le bon ordre, on les permute. On passe ensuite au 2ème et 3ème, etc. - À la fin du premier parcours, on aura poussé le plus grand élément vers sa place finale (à la fin du tableau).
- On recommence cette opération en parcourant de 1 à
n-1puis de 1 àn-2et ainsi de suite. - On arrête quand la partie à trier est réduite à un seul élément ou que le tableau est devenu trié (aucune permutation faite lors du dernier parcours).
3. Le tri à bulle
Principe :
- Le tri à bulle fait remonter les grands éléments vers la fin du tableau.
- Cette migration le long du tableau s'effectue par permutation successive.