Sciences de l'informatique

Bienvenue dans notre forum de partage et d'échange d'information technique dans le domaine NTIC (Informatique, Programmation, Réseau, Multimédia), ce forum est destinée à tous les élèves Tunisiens
 
AccueilCalendrierFAQMembresGroupesS'enregistrerConnexion
Sujets similaires
    Rechercher
     
     

    Résultats par :
     
    Rechercher Recherche avancée
    Derniers sujets
    Navigation
     Portail
     Index
     Membres
     Profil
     FAQ
     Rechercher
    Janvier 2017
    LunMarMerJeuVenSamDim
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
    CalendrierCalendrier
    Qui est en ligne ?
    Il y a en tout 1 utilisateur en ligne :: 0 Enregistré, 0 Invisible et 1 Invité

    Aucun

    Le record du nombre d'utilisateurs en ligne est de 6 le Ven 13 Jan - 2:22

    Partagez | 
     

     Tri de Shell

    Voir le sujet précédent Voir le sujet suivant Aller en bas 
    AuteurMessage
    Dhifallah Fethi
    Admin


    Messages : 74
    Date d'inscription : 02/03/2011

    MessageSujet: Tri de Shell   Mer 2 Mar - 21:30

    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 (en) (né en 1924) qui publia l'algorithme dans le numéro de juillet 1959 de Communications of the ACM.

    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).

    Dans l'exemple ci-dessous, on a choisi successivement 4, 2 et 1 comme distances séparant les éléments à trier à chaque étape et on obtient:

    le vecteur à trier est:
    1 2 3 4 5 6 7 8 9

    6 5 4 9 1 7 8 3 2


    Indiquons le éléments à trier en rouge (de numéros 1, 5 et 9 distants de 4)
    1 2 3 4 5 6 7 8 9

    6 5 4 9 1 7 8 3 2


    On obtient :
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6


    Il faut maintenant trier les éléments de numéro 2 et 6 (toujours distants de 4)
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6


    On obtient:
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6


    Il faut maintenant trier les éléments de numéro 3 et 7 (toujours distants de 4)
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6


    On obtient
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6



    Il faut maintenant trier les éléments de numéro 4 et 8
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6


    On obtient
    1 2 3 4 5 6 7 8 9

    1 5 4 3 2 7 8 9 6


    Il faut maintenant trier les éléments de numéro 5 et 9
    1 2 3 4 5 6 7 8 9

    1 5 4 9 2 7 8 3 6

    On obtient
    1 2 3 4 5 6 7 8 9

    1 5 4 3 2 7 8 9 6


    Dans une deuxième phase, on va trier les éléments dont les numéros ont un écart de 2: 1, 3, 5, 7, 9
    1 2 3 4 5 6 7 8 9

    1 5 4 3 2 7 8 9 6


    On obtient
    1 2 3 4 5 6 7 8 9

    1 5 2 3 4 7 6 9 8


    Ceux de numéros 2, 4, 6, 8
    1 2 3 4 5 6 7 8 9

    1 5 2 3 4 7 6 9 8


    On obtient
    1 2 3 4 5 6 7 8 9

    1 3 2 5 4 7 6 9 8


    Dans une troisième phase, on va trier les éléments dont les numéros ont un écart de 1, à savoir 1, 2, 3, ..., 9 On obtient
    1 2 3 4 5 6 7 8 9

    1 2 3 4 5 6 7 8 9


    Note: Dans la pratique, on choisit souvent ..., 10, 7, 4, 1 comme écarts entre les éléments à trier à chaque étape.
    Et Donald Knuth suggère lui de choisir comme écart:

    p0=0
    P1=3*P0+1
    pi =3*Pi-1 +1
    et de prendre P tel que P<N

    Animation du tri de Shell


    [Vous devez être inscrit et connecté pour voir ce lien]

    Téléchargement de l'animation
    Taille: 98.63 KB
    [Vous devez être inscrit et connecté pour voir ce lien]

    Code en Pascal:(mode itérative)


    Code:
    procedure shell(var t:tab; n:integer);
    var aux,j,i,p:integer;
    begin
      p:=0  ;
      while (p<N) do
        p:=(3*p+1);
      while (p>1)do
      begin
        p:=p div 3;
        for i := p to n do
          begin
            aux:=t[i];
            j:=i;
            while(j>p) and(t[j-p] >aux) do
              begin
                t[j] := t[j-p];
                j:=j-p;

              end;
            t[j]:=aux;
          end;
        end;
    end;

    Code en Pascal:(mode récursive)

    Code:
    Procedure shell (Var t: TAB; n: integer);
    Var aux,i : integer;
    begin
            If n > 1 Then
                begin
                      shell (t,n - 1);
                      If t[n] < t[n - 1] Then
                      Begin
                        aux:= t[n];
                        i := n;
                        Repeat
                            t[i] := t[i - 1];
                            i := i - 1;
                        Until (i = 1) Or (aux > t[i - 1]);
                        t[i] := aux;
                      End;
                      end;
                      end;
    Revenir en haut Aller en bas
    http://ntic.moontada.net
     
    Tri de Shell
    Voir le sujet précédent Voir le sujet suivant Revenir en haut 
    Page 1 sur 1
     Sujets similaires
    -
    » MSN Shell v4.2.27.7 احلي اضافات الماسنجر ويمكنك تشغيل اكثر من ماسنجر

    Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
    Sciences de l'informatique :: 4ème SI :: Programmation :: Cours-
    Sauter vers: