Discussion :

[JetliMohamed]

Bonjour à tous, la méthode de tri shell est très difficile pour moi. J'ai lu des cours très compliqués sur le net, SVP SVP SVP je suis intéressé par cette méthode. Aidez-moi à la comprendre, le probléme pour moi n'est pas seulement ça, mais aussi de traiter ce shell en récursivité {c'est un devoir à la maison}.
S'il vous plaît les gars aidez-moi plus rapidement.

[JetliMohamed]

Voici l'algo en TPW1.5 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
procedure shell (n: integer ; var t:tab ) ;
var
   p,i,k,aux: integer;
begin
     {Calcul pas}
     p:=0;
     while p<= n do
     begin
          p:= 3*p+1
     end;
     p:=p div 3;    
     while p <> 0 do
     begin
          for i:= p+1 to n do
          begin
               if t[i] < t[i-p] then
               begin
                    aux := t[i] ;
                    k:= i-p;
 
 
                    {Décalage à droite}
                    while (k >= p) and (aux < t[k]) do
                    begin
                         t[k+p] := aux;
                         k:=k-p;
                    end;
                    t[k+p]:=aux;
               end;
          end;
          p:=p div 3;
     end;
end;

Et la difficulté est pourquoi, après le décalage à droite, k été sauvegardé dans la valeur K-P et il retourne a t[k+p] pour la donnée la valeur de (aux).

[Mic**]

Mic**

il faut peut être mettre t[k+p]:=aux après k:=k-p
et faire tourner le programme en mode débogage pour vérifier que la boucle s'exécute correctement.

[oualidosphelix]

D'abord, le fameux algorithme du tri shell que l'on peut trouver sur net c'est celui donné par "ningistine".
Le tri shell - comme a eu lidée Mr shell - c'est une optimisation de la méthode de tri par insertion. On sait tous que le tri par insertion est la plus rapide des méthodes pour trier des tableaux de petites dimensions (<=10 elements).
Pour cela, il a introduit la notion de 'pas'. D'abord, on peut retrouver ce 'pas' en utilisant la suite :

p1=1;
p(n+1)=3*p(n)+1;

le pas étant le premier P(m)>=n/9; (n la dimension du tableau).
On trie les petits tableaux par insertion et on prend une nouvelle valeur du pas soit

(pas'=pas/3)

De proche en proche, on arrive finalement à une valeur de 'pas' =1 : un dernier tri par insertion remplira la tâche et le tableau est trié !..

[ningistine]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure trishell (var t:tab; n:integer ) ;
 var    p,i,j,v: integer;
 begin    
     p:=0;
     while p<= n do    
     p:= 3*p+1;
     while p <> 0 do
      begin
          p:=p div 3;
          for i:= p to n do
           begin
                v:=t[i];
                j:=i;
                while (j > p-1) and (t[j-p] > v ) do
                 begin
                      t[j]:=t[j-p];
                      j:=j-p;
                 end;
                t[j]:=v;
           end;
      end;
 end;

[JetliMohamed]

Salut tout le monde,
dans la boucle pour il y a une condition très importante que "ningistine" ne précise pas : c'est de commencer le balayage du compteur (i) à (p+1) et pas (p) parce que, après la différence de (j-p), on pointe vers la position zéro. Pour optimiser cet algorithme, il faut mettre la boucle pour de cette façon, plus (" for i:=p+1 to n do ") pour commencer à la case n° p+1 et pas (p). Je crois que c'est plus optimiste comme ça.

[helal_midou]

slt tt le monde,
dans la bouvcle pour il ya une condition trés importante que "ningistine" ne la dise pas c'est de commencer le balayage du compteur (i) commençant de (p+1) n'est pas (p) parceque aprés la difference de (j-p) on se pointe dans la postion zéros pour optimiser ce algorithme il faut mettre le boucle pour de cette façon plus (" for i:=p+1 to n do ")
pour commencer de la case N° p+1 n'est pas (p) je croix que c'est plus optimiste
comme ça.

non le compteur se deplace automatiquement (
0)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
debut trier(n:entier; var t:tab)
p<--0
tant que (p<n)faire 
p<--3*p+1
fin tant que 
tant que (p<>0)faire
p<---p div 3
pour i de p à n faire
  valeur <---t[i]
       j<--- i
fin tant que
tant que (j>p-1)  ET (T[j-p]>valeur) faire
t[j]<---t[j-p]
j<--- j-p
fin tant que
t[j]<---valeur
fin pour fin tant que
fin trier

[JetliMohamed]

Bonjours hela_midou c'est vraiment impeccable comme leçon, merci de m'avoir expliqué cette méthode de tri-là et je souhaite que ce ne soit pas la dernière difficulté.

Merci à tous [Jlidi_Mohamed]

[helal_midou]

Remarque :
Le tri shell trie chaque liste d'élements séparés de p positions chacun avec le tri par insertion. L'alghorithme effectue plusieurs fois cette opération en diminuant p jusqu'à p égal à 1, ce qui équivaut à trier tous les éléments ensemble.

Exemple :
Nous proposons d'utiliser la méthode du tri shell pour trier un tableau t d'entiers en ordre croissant.
- Considérons le tableau T contenant les 15 élément suivants:

_____________________________________________________________
T [ -5] [30] [0] [-2] [42] [22] [9] [-4] [10] [15] [40] [-9] [12] [28] [14]
----------------------------------------------------------------------

• Etape 1 :
  La première action à faire consiste à déterminer la valeur maximale de pas.
• Etape 2 :
  N.B. : en utilisant l'expression p <--- (p-1) div 3, nous pouvons déduire que les valeurs que prendra le pas p sont 4 et 1.
  • Etape 2.1 :
    pour p=4, nous appliquons le tri par insertion pour chacun des sous-vecteurs de pas 4 en commençant par l'element d'indice1; puis l'élément d'indice2; etc...
    • Trions par insertion linéaire le sous-vecteur qui regroupe les composantes 1, 5, 9 et 13 et qui ont pour valeur respective : -5, 42, 10, 12.
      
      Nous allons obtenir le tableau suivant :
      

      _____________________________________________________________
      T [ -5] [30] [0] [-2] [10] [22] [9] [-4] [12] [15] [40] [-9] [42] [28] [14]
      ----------------------------------------------------------------------

      Remarquez que les valeurs des cases d'indices 1, 5, 9, 13 sont triées par ordre croissant.
      
    • Trions par insertion linéaire le sous-vecteur qui regroupe les composantes 2, 6, 10 et 4 qui ont pour valeur respective : 30 , 22 ,15 et 28.
      
      Nous allons obtenir le tableau suivant :
      

      _______________________________________________________________
      T [ -5] [15] [0] [-2] [10] [22] [9] [-4] [12] [28] [40] [-9] [42] [30] [14]
      ------------------------------------------------------------------------

      Remarquez que les valeurs des cases d'indices 2, 6, 10 et 14 sont triées par ordre croissant.
      
    • Quels sont les indices des éléments à trier en 3 ème lieu ? Donnez le contenu de tableau T aprés avoir réalisé cette étape.
      
    • Même question pour la 4 ème opération.
    
    
  • Etape 2.2 :
    
    Pour p=1 nous appliquons le tri par insertion pour chacun des sous-vecteurs de pas 1. Ce qui revient à appliquer le tri par insertion simple à tout le tableau.

Code source du tri shel en Pascal :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure trier_shel(n:entier ; var t:tab);
procedure shell (n: integer ; var t:tab ) ;
var    p,i,j,valeur: integer;
 begin    
     p:=0;
     while p < n do    
     p:= 3*p+1;
     while p > 0 do
      begin
          p:=p div 3;
          for i:= p to n do
           begin
                valeur:=t[i];
                j:=i;
                while (j > p-1) and (t[j-p] > valeur ) do
                 begin
                      t[j]:=t[j-p];
                      j:=j-p;
                 end;
                t[j]:=valeur;
           end;
      end;
 end;

[droggo]

Dio,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure trier_shel(n:entier ; var t:tab);
procedure shell (n: integer ; var t:tab ) ;
var    p,i,j,valeur: integer;
 begin    
     p:=0;
     while p < n do    
     p:= 3*p+1;
     while p > 0 do
      begin
          p:=p div 3;
          for i:= p to n do
           begin
                valeur:=t[i];
                j:=i;
                while (j > p-1) and (t[j-p] > valeur ) do
                 begin
                      t[j]:=t[j-p];
                      j:=j-p;
                 end;
                t[j]:=valeur;
           end;
      end;
 end;

Pas trace de récursivité là-dedans. C'est normal, c'est l'algorithme habituel, mais ne résout pas la question qui demande une version récursive (ce qui est absurde, comme pour le tri à bulles dans un autre sujet ).

[JetliMohamed]

wi c vraiment ce que tu dis il n'ya pas aucune recurcivité dans cet algo je veut dire céça mon problème (tri shell récurcif) qui n'a pas de solution s'ils vous plait
tous ce qui peut m'aider alors ne pas rater.
et merci beaucoup pour tous

[Jlidi Mohamed]

[niz208]

Dans le programme principal on met :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
....
pas <--0
repeat
pas<-- pas * 3 +1
until pas <-- n 
tri(t,n,pas)
.....

et on declare une procedure tri recursif comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
0) debut proedure tri(var t:tab; n:entier; var pas : entier)
1) pas <-- pas div 3
2) pour i de pas + 1 a n faire
    xx <-- t[i]
    si t[i] < t[i-pas] alors
        proc decaller(t,i-pas, pos)
        t[pos] <-- xx
    fin si
3) Si pas <> 1 alors
     proc tri[/B](t,n,pas)
    fin si
4) Fin procedure tri.
 
0) debut procedure decaller(var t:tab; y:entier; var pos)
1) pos <--y
2) repeter
    t[pos+pas ] <-- t[pos]
    pos <-- pos-pas
   jusqu'a (pos < = 0 ) ou (t[pos] < = xx)
3) pos <-- pos + pas
4) Fin procedure decaller

[the_cha0s]

Remarque :
Le tri shell trie chaque liste d'élements séparés de p positions chacun avec le tri par insertion. L'alghorithme effectue plusieurs fois cette opération en diminuant p jusqu'à p égal à 1, ce qui équivaut à trier tous les éléments ensemble.

Exemple :
Nous proposons d'utiliser la méthode du tri shell pour trier un tableau t d'entiers en ordre croissant.
- Considérons le tableau T contenant les 15 élément suivants:

• Etape 1 :
  La première action à faire consiste à déterminer la valeur maximale de pas.
• Etape 2 :
  N.B. : en utilisant l'expression p <--- (p-1) div 3, nous pouvons déduire que les valeurs que prendra le pas p sont 4 et 1.
  • Etape 2.1 :
    pour p=4, nous appliquons le tri par insertion pour chacun des sous-vecteurs de pas 4 en commençant par l'element d'indice1; puis l'élément d'indice2; etc...
    • Trions par insertion linéaire le sous-vecteur qui regroupe les composantes 1, 5, 9 et 13 et qui ont pour valeur respective : -5, 42, 10, 12.
      
      Nous allons obtenir le tableau suivant :
      
      
      Remarquez que les valeurs des cases d'indices 1, 5, 9, 13 sont triées par ordre croissant.
      
    • Trions par insertion linéaire le sous-vecteur qui regroupe les composantes 2, 6, 10 et 4 qui ont pour valeur respective : 30 , 22 ,15 et 28.
      
      Nous allons obtenir le tableau suivant :
      
      
      Remarquez que les valeurs des cases d'indices 2, 6, 10 et 14 sont triées par ordre croissant.
      
    • Quels sont les indices des éléments à trier en 3 ème lieu ? Donnez le contenu de tableau T aprés avoir réalisé cette étape.
      
    • Même question pour la 4 ème opération.
    
    
  • Etape 2.2 :
    
    Pour p=1 nous appliquons le tri par insertion pour chacun des sous-vecteurs de pas 1. Ce qui revient à appliquer le tri par insertion simple à tout le tableau.

Code source du tri shel en Pascal :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure trier_shel(n:entier ; var t:tab);
procedure shell (n: integer ; var t:tab ) ;
var    p,i,j,valeur: integer;
 begin    
     p:=0;
     while p < n do    
     p:= 3*p+1;
     while p > 0 do
      begin
          p:=p div 3;
          for i:= p to n do
           begin
                valeur:=t[i];
                j:=i;
                while (j > p-1) and (t[j-p] > valeur ) do
                 begin
                      t[j]:=t[j-p];
                      j:=j-p;
                 end;
                t[j]:=valeur;
           end;
      end;
 end;

salut je viens de m'inscrire sur ce site vu qu'il est intéressant !!
j'ai pas compris dans la deuxième étape quand l'algo commencera a trier les sous vecteurs !! quand j'exécute l'algo il compare seulement deux sous-vecteurs : (1 et 5,puis 2 et 6....) , vous pouvez me détaillez s'il vous plait l'étape où il compare dans cette exemple les cases : 1,5,9 et 13

[oussamadag]

Salut tout monde,
Merci pour ça, Moi aussi je suis intéressé par cette nouvelle méthode de tri j'ai cherche dans internet mais j'ai pas trouvé de code en pascal bien commente pour le tri shell en récursif

quelle est le plus rapide le tri shell ou tri par fusion????

[adel_info]

le premier pas = 13
deuxième pas = 4
dernier pas =1