Tri shell

[the_cha0s]

Envoyé par 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:

• 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 :

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????

[oussamadag]

salut,
c'est la procédure de tri shell en récursif

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
Procedure TriShell_Recursif (Var t:tab; n,h:integer);
                	Var
   	              aux,i : integer;
		begin
    		      If h > 0 Then
    			Begin
        		      If n > h Then
             			begin
                  			TriShell_Recursif (t,n - h,h);
                  				If t[n] < t[n - h] Then
                  					Begin
                     						aux:=t[n];
                     						i:=n;
                     						Repeat
									t[i] := t[i - h];
									i := i - h;
								Until (i = h) Or (aux > t[i - h]);
									t[i] := aux;
							End;
				End;
				TriShell_Recursif (t,n,h Div 3);
			 End;
		End;

[adel_info]

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

[adel_info]

c est quoi h
quelle est la valeur initiale de h