IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Pascal Discussion :

Tri shell


Sujet :

Pascal

  1. #1
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut Tri shell
    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.

  2. #2
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut
    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).

  3. #3
    Candidat au Club
    Inscrit en
    Janvier 2008
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 1
    Points : 4
    Points
    4
    Par défaut
    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;

  4. #4
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut
    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.

  5. #5
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 4
    Points : 5
    Points
    5
    Par défaut
    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;

  6. #6
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 4
    Points : 5
    Points
    5
    Par défaut
    Citation Envoyé par JetliMohamed Voir le message
    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

  7. #7
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut
    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]

  8. #8
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 941
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 941
    Points : 5 652
    Points
    5 652
    Par défaut
    Dio,
    Citation Envoyé par helal_midou Voir le message
    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 ).
    Si les cons volaient, il ferait nuit à midi.

  9. #9
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut
    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]

  10. #10
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 11
    Points : 6
    Points
    6
    Par défaut tri-shell recursif
    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

  11. #11
    Membre à l'essai
    Inscrit en
    Décembre 2007
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : Décembre 2007
    Messages : 24
    Points : 21
    Points
    21
    Par défaut
    Merci, mais ce que j'ai pas compris c'est cette phrase là :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Si pas <> 1 alors
         proc tri[/b](t,n,pas)
        fin si
    C'est vrai c'est un appel mais plus exactement, qu'est ce que "[/b]" ???

  12. #12
    Expert confirmé
    Avatar de Loceka
    Profil pro
    Inscrit en
    Mars 2004
    Messages
    2 276
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2004
    Messages : 2 276
    Points : 4 845
    Points
    4 845
    Par défaut
    Le [/b] est juste une erreur de balisage

    La balise "B" sert à mettre le éléments en gras, le code qu'il voulait écrire était :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Si pas <> 1 alors
      proc tri(t,n,pas)
    fin si

  13. #13
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 4
    Points : 5
    Points
    5
    Par défaut
    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
    procedure shell (n: integer ; var t:tab ;var p:integer ) ;
    var
       i,x: integer;
         begin
        p:=p div 3 ;
    
        for i:= p+1 to n do
    
       x:=t[i];
     if t[i]<t[i-p] then
           decaller(t,i-p );pos());
        t[pos]:=x;
        end;
       if p<> 1 then
            shell (t,n,p);
        end;
        end;
    la curseur arrete dans la zone rouge
    et m 'affiche cette error: string expression expected

  14. #14
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    11
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 11
    Points : 6
    Points
    6
    Par défaut
    au lieu d'ecrire
    decaller(t,i-p );pos());
    on ecrit :
    decaller(t,i-p ,pos);

  15. #15
    Futur Membre du Club
    Inscrit en
    Janvier 2008
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Janvier 2008
    Messages : 4
    Points : 5
    Points
    5
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    decaller(t,i-p {cuseur ici},pos);
    donc pour quoi il m affiche error?

    error89 :')'expected

  16. #16
    Membre du Club
    Inscrit en
    Juillet 2006
    Messages
    294
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 294
    Points : 59
    Points
    59
    Par défaut
    Salut
    Moi aussi je suis interesser par cette nouvelle methode de tri j'ai cherche dans le net mais j'ai pas trouver un code en pascal bien commente pour tri shell recurssif
    j'esper que vous pouvez m'aidez

  17. #17
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 941
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 941
    Points : 5 652
    Points
    5 652
    Par défaut
    Hia,
    Citation Envoyé par ALIAS200 Voir le message
    Salut
    Moi aussi je suis interesser par cette nouvelle methode de tri j'ai cherche dans le net mais j'ai pas trouver un code en pascal bien commente pour tri shell recurssif
    j'esper que vous pouvez m'aidez
    Tu n'as pas dû chercher bien longtemps.

    Le web fourmille de pages parlant de cet algorithme, et un des premiers liens renvoyés par Google pour la recherche tri shell récursif est justement une implémentation en Pascal.

    Accessoirement, cette méthode n'a rien de nouveau.
    Si les cons volaient, il ferait nuit à midi.

  18. #18
    Membre averti Avatar de Tux++
    Étudiant
    Inscrit en
    Avril 2008
    Messages
    281
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2008
    Messages : 281
    Points : 379
    Points
    379
    Par défaut
    bonjour,

    en effet, ce n'est pas nouveau.

    Par contre, ce tri n'est pas très stable, bien qu'évolution au niveau de la rapidité par rapport au tri par insertion, il faut choisir à chaque fois un espacement entre les éléments adéquat, et donc la généralisation bof bof...La complexité est fort variante selon l'échantillon de données.

    Certified Oracle Advanced PL/SQL Professional
    Certified Oracle APEX Expert
    Certified Oracle SQL Expert

  19. #19
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 941
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 941
    Points : 5 652
    Points
    5 652
    Par défaut
    Hia,
    Citation Envoyé par Tux++ Voir le message
    bonjour,

    en effet, ce n'est pas nouveau.

    Par contre, ce tri n'est pas très stable, bien qu'évolution au niveau de la rapidité par rapport au tri par insertion, il faut choisir à chaque fois un espacement entre les éléments adéquat, et donc la généralisation bof bof...La complexité est fort variante selon l'échantillon de données.

    Ce n'est pas le seul tri dans ce cas, ce n'est pas trop à prendre en compte.

    Sauf cas particulier, genre données souvent presque classées, ou au contraire très aléatoires, il faut choisir le tri utilisé sur des données réelles, et choisir celui qui, en moyenne, est le plus performant.
    Sans oublier que la quantité de données intervient également, bien entendu.
    Si les cons volaient, il ferait nuit à midi.

  20. #20
    Membre averti
    Avatar de Mic**
    Homme Profil pro
    Retraité
    Inscrit en
    Avril 2007
    Messages
    57
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 76
    Localisation : France, Sarthe (Pays de la Loire)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Avril 2007
    Messages : 57
    Points : 409
    Points
    409
    Billets dans le blog
    2
    Par défaut Tri shell
    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.

Discussions similaires

  1. besoin d'aide sur tri shell
    Par eaglevmt-4 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 30/12/2008, 18h35
  2. Tri shell : problème de décalage
    Par petit programmeur dans le forum Pascal
    Réponses: 14
    Dernier message: 22/02/2008, 23h39
  3. GAP du tri Shell
    Par katrena99 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 11/01/2008, 20h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo