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.