Tri de shell

Tri de shell

Tri de Shell

Le tri de Shell ou Shell Sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution mais ce tri n'est pas stable. Il est facile de comprendre intuitivement comment fonctionne cet algorithme mais il est difficile de calculer son temps d'exécution.

Le nom vient de son inventeur Donald Shell (1928-) (voir en:Donald Shell) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM.

Sommaire

Fonctionnement

Le tri de Shell est une amélioration du tri par insertion en observant deux choses:

  • Le tri par insertion est efficace si la liste est à peu près triée. (1)
  • Le tri par insertion est inefficace en moyenne car il ne déplace les valeurs que d'une position par instruction. (2)

Le tri de Shell trie chaque liste d'éléments séparés de n positions chacun avec le tri par insertion. L'algorithme effectue plusieurs fois cette opération en diminuant n jusqu'à n=1 ce qui équivaut à trier tous les éléments ensemble.

Le fait de commencer avec des éléments espacés permet de pallier l'inconvénient (2), tandis que lorsque l'on fait à la fin avec un espacement de 1, ce qui est en fait un tri par insertion ordinaire, on tire parti de l'avantage (1).

Rapidité

Sur des tableaux de moins d'une centaine d'éléments, ce tri est aussi rapide qu'un tri rapide simple. Mais plutôt que d'être en compétition avec l'algorithme quicksort, il peut être utilisé pour son optimisation quand les sous-listes à traiter deviennent petites.

Le choix de l'espacement entre les éléments qu'on trie à chaque étape (gap) est très important. Il peut faire varier le temps d'exécution de O(n2) à O(nlog2n), peut-être, O(nlogn). C'est un sujet de recherche.

Gap ou espacement entre les éléments

Les premiers espacements optimaux (empiriquement trouvés) sont les suivants : 1, 4, 10, 23, 57, 132, 301, 701.

On remarque que le facteur entre ces valeurs, exception faite des deux premières, est d'environ 2,3. On peut effectivement prolonger cette liste avec ce facteur si les dimensions du tableau dépassent environ 1600 éléments. Par exemple pour trouver le premier gap en Pascal :

  gap := 701;
  while gap<length(liste) do gap := round(gap*2.3);

Puis à chaque itération, si on utilise un gap calculé :

  gap := round(gap/2.3);

Exemple d'implémentation

Shell Sort en C

/*
 * Exécute un tri par insertion avec la séparation donnée
 * If gap == 1, on fait un tri ordinaire.
 * If gap >= length, on ne fait rien.
 */
void shellSortPhase(int a[], int length, int gap) {
    int i;
 
    for (i = gap; i < length; ++i) {
        int value = a[i];
        int j;
        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
            a[j + gap] = a[j];
        }
        a[j + gap] = value;
    }
}
 
void shellSort(int a[], size_t length) {
    /*
     * gaps[] doit approximer une Série géométrique.
     * La sequence suivante est la meilleure connue en terme
     * de nombre moyen de comparaisons. voir:
     * http://www.research.att.com/~njas/sequences/A102549
     */
    static const int gaps[] = {
        1, 4, 10, 23, 57, 132, 301, 701
    };
    int sizeIndex;
 
    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
               sizeIndex >= 0;
               --sizeIndex)
        shellSortPhase(a, length, gaps[sizeIndex]);
}

Shell Short en Pascal

Implémention du tri Shell en Pascal (par ordre croissant).

procedure TriShell(n : integer ; var t : tab);
var
  p, k, i, j : integer;
begin
  (* Recherche du Gap optimal qui est le résultat de *)
  (* la suite récurrente : Un = 3.Un-1 + 1           *)
  (* Tel que Un < n (Nombre d'éléments du tableau)   *)
  p := 0;
  while (p < n) do p := 3 * p + 1;
 
  while (p <> 0) do
  begin
    (* On affine peu à peu le Gap            *)
    (* Gap = 1 ==> Tri par Insertion ordinaire *)
    p := p div 3;
    for i := p to n do
    begin
      k := t[i]; (* Valeur à insérer *)
 
      (* Recherche de la position d'insertion *)
      j:= i;
      while (j > p - 1) and (t[j - p] > k) do
      begin
        t[j] := t[j - p];
        j := j - p;
      end;
 
      (* Insertion de la valeur à son emplacement *)
      t[j] := k;
    end;
  end;
end;

Shell Sort en Java

public static void triDeShell(int [] tab,int tailleLogique){
   int pas = 1;
   while( pas < tailleLogique/9) {
      pas = pas*3 + 1; // on fixe le premier pas
   }
   while (pas > 0) {  // boucle sur les différents pas         
      for(int série = 0; série <= pas-1; série ++) {  // boucle sur les séries
         int positionEltAInsérer = série + pas;  // tri par insertion
 
         while(positionEltAInsérer < tailleLogique) {
            int élémentAInsérer = tab[positionEltAInsérer];
            int posElemComparé = positionEltAInsérer - pas;
 
            while ((posElemComparé >= 0) && (élémentAInsérer < tab[posElemComparé])) {
               tab[posElemComparé + pas] = tab[posElemComparé];
               posElemComparé -= pas;
            }
            tab [posElemComparé + pas] = élémentAInsérer;
            positionEltAInsérer += pas;
         }
      }         		
   pas = pas/3;	
   }      
}

Shell Sort en C#

using System;
public class ShellSorter
{
  public void Sort(int [] list)
 
 
  {
      int inc;
      for(inc=1;inc<=list.Length/9;inc=3*inc+1);
      for(;inc>0;inc/=3)
      {
          for(int i=inc+1;i<=list.Length;i+=inc)
        {
          int t=list[i-1];
          int j=i;
          while((j>inc)&&(list[j-inc-1]>t))
          {
            list[j-1]=list[j-inc-1];
            j-=inc;
          }
          list[j-1]=t;
        }
      }
    }
}
public class MainClass
{
    public static void Main()
    {
    int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
    ShellSorter sh=new ShellSorter();
    sh.Sort(iArrary);
    for(int m=0;m<=13;m++)
    Console.WriteLine("{0}",iArrary[m]); 
      }
}

Liens externes

Les algorithmes de tri

à bulle • par sélection • par insertion • par tas • par base • rapide • smoothsort • fusion • comptage • de Shell
Ce document provient de « Tri de Shell ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tri de shell de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Tri de Shell — Le tri de Shell ou Shell Sort en anglais est un algorithme de tri. C est une amélioration notable du tri par insertion au niveau de la vitesse d exécution mais ce tri n est pas stable. Il est facile de comprendre intuitivement comment fonctionne… …   Wikipédia en Français

  • Tri stable — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

  • Shell — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir Schell. Sur les autres projets Wikimedia : « Shell », sur …   Wikipédia en Français

  • Tri par insertion — Exemple du tri par insertion utilisant une liste de nombres aléatoires Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C est le tri que la plupart des personnes utilisent naturellement pour trier des… …   Wikipédia en Français

  • tri|ton — «TRY tuhn», noun. 1. a) Greek Mythology. a sea god, son of Poseidon and Amphitrite, having the head and body of a man and the tail of a fish and carrying a trumpet made of a conch shell. b) (later) any one of a group of minor sea gods by whom… …   Useful english dictionary

  • Tri|ton — «TRY tuhn», noun. 1. a) Greek Mythology. a sea god, son of Poseidon and Amphitrite, having the head and body of a man and the tail of a fish and carrying a trumpet made of a conch shell. b) (later) any one of a group of minor sea gods by whom… …   Useful english dictionary

  • Tri a bulles — Tri à bulles Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d une liste, comme les bulles d… …   Wikipédia en Français

  • Tri fusion — appliqué à un tableau de 7 éléments. Le tri fusion est un algorithme de tri stable par comparaison. Sa complexité temporelle pour une entrée de taille n est de l ordre de n log n, ce qui est asymptotiquement optimal. Le tri fusion se décrit… …   Wikipédia en Français

  • Tri par selection — Tri par sélection Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l on va replacer à sa position finale c est à dire en… …   Wikipédia en Français

  • Tri radix — Tri par base Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”