Tri Gnome

Le tri Gnome

Cet algorithme a été d'abord proposé en 2000 - sous le nom de "tri stupide" - par le Dr. Hamid Sarbazi-Azad (Professeur à l'université de Sharif, une des plus grandes universités d'Iran) puis redécouvert plus tard par Dick Grune (le premier développeur de CVS) qui l'appela "gnome sort" (parce qu'il parait que c'est la méthode qu'utilisent les nains de jardin hollandais pour trier une rangée de pots de fleurs).

L'algorithme est similaire au tri par insertion, sauf que, au lieu de insérer directement l'élément à sa bonne place, l'algorithme effectue une série de permutations, comme dans un tri bulle.

L'animation ci-après illustre le fonctionnement de ce tri :

Démonstration du tri "Gnome"

  1. PROCEDURE tri_Gnome(tableau[])
  2.     pos ← 1
  3.     TANT QUE pos < longueur(tableau)
  4.         SI (tableau[pos] >= tableau[pos-1])
  5.             pos ← pos + 1
  6.         SINON
  7.             echanger tableau[pos] ET tableau[pos-1]
  8.             SI (pos > 1)
  9.                 pos ← pos - 1
  10.             FIN SI
  11.         FIN SI
  12.     FIN TANT QUE
  13. FIN PROCEDURE
  1. let bulle tableau p =
  2.     let i_b = ref p in
  3.     while (!i_b>0) && (tableau.(!i_b) < tableau.(!i_b - 1)) do
  4.         let t = tableau.(!i_b) in
  5.         begin
  6.             tableau.(!i_b) <- tableau.(!i_b - 1);
  7.             tableau.(!i_b - 1) <- t;
  8.         end;
  9.         i_b := !i_b - 1;
  10.     done;;
  11.  
  12.  
  13. let  tri_gnome tableau =
  14.     for i_i = 1 to (Array.length tableau) - 1 do
  15.         if tableau.(i_i) < tableau.(i_i - 1) then bulle tableau i_i;
  16.     done;
  17.     tableau;;
  1. type tab = array[1..20] of integer;
  2.  
  3. procedure tri_gnome(var tableau : tab);
  4. var
  5.    i_b, i_i, t  : Integer;
  6.     (* i_b : indice utilisé pour le tri bulle
  7.     i_i : indice pour e tri par insertion *)
  8. begin
  9.     i_b := 1;
  10.     i_i := 2;
  11.     while i_b <= 20 do
  12.     begin
  13.         if tableau[i_b-1] <= tableau[i_b] then
  14.         begin
  15.             i_b := i_i;
  16.             i_i := i_i + 1
  17.         end else
  18.         begin
  19.             t := tableau[i_b-1];
  20.             tableau[i_b-1] := tableau[i_b];
  21.             tableau[i_b] := t;
  22.             i_b := i_b - 1;
  23.             if i_b = 0 then
  24.             begin
  25.                 i_b := i_i;
  26.                 i_i := i_i + 1
  27.             end
  28.         end
  29.     end;
  30. end;
  31.  
  1. def tri_gnome(tableau):
  2.     i_b,i_i,taille = 1,2,len(tableau)
  3.     while i_b < taille:
  4.         if tableau[i_b-1] <= tableau[i_b]:
  5.             i_b,i_i = i_i, i_i+1
  6.         else:
  7.             tableau[i_b-1],tableau[i_b] = tableau[i_b],tableau[i_b-1]
  8.             i_b -= 1
  9.             if i_b == 0:
  10.                 i_b,i_i = i_i, i_i+1
  11.     return tableau
  1. void bulle(int* tableau, int p) {
  2.     int i_b = p;
  3.     while ((i_b>0) && (tableau[i_b]<tableau[i_b - 1])) {
  4.         int t = tableau[i_b -1];
  5.         tableau[i_b - 1]= tableau[i_b];
  6.         tableau[i_b ] = t;
  7.         i_b --;
  8.     }
  9. }
  10.  
  11. void tri_gnome (int* tableau) {
  12.     for (int i_i=0;i_i<20;i_i++) bulle(tableau,i_i);
  13. }

Si on utilise cette méthode pour résoudre le problème de la page précédente, on a :



 


Les graphiques ci-dessous montrent la progression du nombre d'opérations en fonction du nombre d'éléments à trier.

Complexité du tri Gnome

Dans le meilleur des cas, avec des données déjà triées, l'algorithme fonctionne comme un tri par insertion. Sa complexité dans le meilleur des cas est donc en Θ(n).

Complexite du tri Gnome dans le meilleur des cas Nombre d'opérations Nombre d'elements à trier Θ(n)

Dans le pire des cas, avec des données triées à l'envers, la complexité du tri Gnome en Θ(n2).

Complexite du tri Gnome dans le pire des cas Nombre d'opérations Nombre d'elements à trier Θ(n2)

Si tous les éléments de la série à trier sont distincts et que toutes leurs permutations sont équiprobables, la complexité en moyenne de l'algorithme est en Θ(n2).

Vou pouvez utiliser cet outil pour le vérifier.

Complexite du tri Gnome en moyenne Nombre d'opérations Nombre d'elements à trier Θ(n2)
>