ALGORITHME DE TRI
Il existe de nombreux algorithmes de tri, je tenterais seulement de
vous montrer les plus populaires et les plus utilisés.
Il n'y a pas vraiment de tri qui soit meilleur que les autres, la vitesse d'exécution d'un algorithme dépend des
donnés à trier. Certains algorithmes sont plus efficaces dans certaines circonstances c'est ce que nous tenterons de
vous montrer
Complexité
Dans le but de mesurer la complexité d'un algorithme de tri,deux quantités sont à observer :
- le nombre d'échanges effectués,
- le nombre de comparaisons effectués entre éléments du tableau.
Grand O
Le grand O est utilisé pour indiquer la croissance d'une fonction. Le symbole utilisé est O.
Grand oméga
Le grand oméga est utilisé pour avoir la limite
inférieur d'une fonction, en d'autre mot le minimum. Le symbole
utilisé est Ω
Les tries
Buble sort
Ce type de tri est le plus simple, mais souvent le moins efficace. Il peut s'avérer utile pour des petits tris étant
donné sa simplicité, il y a peu de chance de faire des erreurs.
L'idée du buble sort est de comparer un élément à son voisin et de les permuter si l'élément est
plus grand que celui-ci.
procedure BubbleSort(var tabNote: array of Integer);
var
i,j: integer;
temp: integer;
begin
for i := high(tabNote) downto low(tabNote) do
for j := low(tabNote) to high(tabNote)-1 do
if tabNote[j] >tabNote[j + 1] then
begin
temp := tabNote[j];
tabNote[j] := tabNote[j + 1];
tabNote[j + 1] := temp;
end;
end;
Comme vous pouvez le voir un tel algorithme est lent, imaginez trier 1000 000 de donnés avec ça.
Vous pouvez remarquer que lorsqu'on change de position l'élément, il arrive souvent que le tableau soit trié
avant que l'algorithme soit fini. On peut aisément améliorer cela en ajoutant une petite vérification.
procedure BubbleSort(var tabNote: array of Integer);
var
i,j: integer;
temp: integer;
Test: Boolean;
begin
for i := low(tabNote) to high(tabNote) do begin
Test := false;
for j := low(tabNote) to high(tabNote) - 1 do begin
if tabNote[j] > tabNote[Succ(j)] then begin
temp := tabNote[j];
tabNote[j] := tabNote[Succ(j)];
tabNote[Succ(j)] := temp;
Test := true;
end;
end;
if not Test then break;
end;
end;
Complexité
La complexité est O(n^2) pour des données mélangées, mais l'approche est O(n) si la liste est presque trié au début.
Insertionsort
Cette méthode est semblable à celle que nous utilisons lorsqu'on trie des cartes. Nous prenons chaque nouvelle
carte et nous l'insérons à la bonne position dans le paquet déjà trié. Ce tri est particulièrement rapide lorsqu'il
y a peu de désordre.
procedure Insertionsort(var tabNote: array of Integer);
var
i, j: Integer;
temp: Byte;
begin
tabNote[0] := 0; //garde l'algo hors de l'alignement
for i := 2 to high(tabNote) do begin
//débute à 2 puisque le premier élément
//n'est ni plus petit
//ni plus grand que lui-même
temp := tabNote[i] ;
j := i;
while tabNote[Pred(j)] > temp do
begin
tabNote[j] := tabNote[Pred(j)];
dec(j);
end;
tabNote[j] := temp; //insère l'élément à la position trouvé
end;
end;
Complexité
Le meilleur cas est n et le pire cas est O(n2)
Shellsort
Ce tri est similaire à l'insertionsort. Il est un peu plus
performant. L'insertionsort n'est pas très rapide puisque les
éléments sont bougés d'un espace à la fois.
Nous pouvons le faire bouger de plusieurs espaces, jusqu'à
ce que nous trouvions le bon emplacement. Pour arriver à une
telle solution, nous pouvons réduire la grosseur de k, chaque
fois que nous constatons que (j-k) ième élément est
plus grand que l'élément actuel. Nous pouvons diviser k
par 3 chaque fois.
procedure ShellSort(var A : ArrayType; N : integer);
var
Done : boolean;
Jump,I,J : integer;
begin
Jump := N;
while (Jump > 1) do
begin
Jump := Jump div 2;
repeat
Done := true;
for J := 1 to (N - Jump) do
begin
I := J + Jump;
if (A[J] > A[I]) then
begin
Swap(A[J], A[I]);
Done := false
end;
end;
until Done;
end
end;
Quicksort
Quicksort est l'algorithme de tri le plus populaire. Sur une entré aléatoire, Quicksort est le plus rapide des
algorithmes que je connais. Quicksort est implanté de façon récursif, il peut ainsi être plus complexe à comprendre.
1. On doit spécifier un élément x pour établir l'alignement.
2. Chaque élément plus petit que x sera mis à droite et ceux plus grand à gauche.
3. Quicksort s'appelle et passe les deux parties. Lorsqu'il est appelé avec un tableau de grosseur 1, un élément a
été trié.
4. Lorsque quicksort revient de la récursion, les deux parties ont été triées et peuvent être mises ensemble.
procedure Quicksort(var tabNote: TArray,longueur, r: Integer);
var
i, j: Integer;
temp, old: Byte;
begin
old := tabNote[(longueur + r) div 2];
i := longeur;
j := r;
repeat
while tabNote[i] < old do inc(i);
while old < tabNote[j] do dec(j);
if i <= j then
begin
temp := tabNote[i];
tabNote[i] := tabNote[j];
tabNote[j] := temp;
inc(i);
dec(j);
end;
until i > j;
if longeur < j then Quicksort( longueur, j);
if i < r then Quicksort( i, r);
end;
Complexité
Le pire cas est O(n2).
La moyenne des résultats : O(n log n)..
Selection Sort
Ce tri parcourt le tableau à trier, cherche l'élément à remplacer et le permute. Ce tri peut
s'avérer intéressant, s'il y a peu d'affectation (fichier).
procedure SelectionSort(var tabNote: array of Integer);
var
I, J, temp: Integer;
begin
for I := Low(tabNote) to High(tabNote) - 1 do
for J := High(tabNote) downto I + 1 do
if tabNote[I] > tabNote[J] then
begin
temp := tabNote[I];
tabNote[I] := tabNote[J];
tabNote[J] := temp;
end;
end;
Complexité
La moyenne des résultats :O( n^2).
Un programme utilisant de nombreux algorithmes de tri est disponible
ici.
