Publicité
+ Répondre à la discussion
Page 2 sur 2 PremièrePremière 12
Affichage des résultats 21 à 26 sur 26

Discussion: Tri shell

  1. #21
    Candidat au titre de Membre du Club
    Profil pro
    Étudiant
    Inscrit en
    novembre 2008
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2008
    Messages : 25
    Points : 12
    Points
    12

    Par défaut Tri shell

    Citation Envoyé par helal_midou Voir le message
    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 :
    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

  2. #22
    Futur Membre du Club
    Profil pro oussama dagdoug
    Inscrit en
    janvier 2010
    Messages
    30
    Détails du profil
    Informations personnelles :
    Nom : oussama dagdoug
    Âge : 22

    Informations forums :
    Inscription : janvier 2010
    Messages : 30
    Points : 19
    Points
    19

    Par défaut

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

  3. #23
    Futur Membre du Club
    Profil pro oussama dagdoug
    Inscrit en
    janvier 2010
    Messages
    30
    Détails du profil
    Informations personnelles :
    Nom : oussama dagdoug
    Âge : 22

    Informations forums :
    Inscription : janvier 2010
    Messages : 30
    Points : 19
    Points
    19

    Par défaut

    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;

  4. #24
    Invité de passage
    Inscrit en
    janvier 2009
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : janvier 2009
    Messages : 8
    Points : 3
    Points
    3

    Par défaut

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

  5. #25
    Invité de passage
    Inscrit en
    janvier 2009
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : janvier 2009
    Messages : 8
    Points : 3
    Points
    3

    Par défaut

    c est quoi h
    quelle est la valeur initiale de h

  6. #26
    Invité de passage
    Homme Profil pro oualid anonim
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Nom : Homme oualid anonim
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : décembre 2012
    Messages : 2
    Points : 2
    Points
    2

    Par défaut tri shell

    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é !..

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •