comprendre le tri de shell

Le
bpascal123
Bonjour,

Je m'excuse en premier de ne pas suivre par une réponse mes derniers
posts, ce n'est pas par manque de respect mais en partie parce qu'on
m'a dit de ne pas trop perdre de temps avec certains aspects du
langage c (notamment la saisie de caractères) Je sais que ce n'est
pas une raison pour ne pas répondre mais je lis avec attention vos
réponses et j'applique les conseils qui reviennent le plus souvent
Certaines fois, je ne prends pas en compte la réponse d'une personne
d'expérience car je ne perçois immédiatement l'utilité de faire
l'effort de changer quelque chose dans le code mais par la suite je me
rends compte que c'est plein de sens.

Je suis actuellement "coincé" sur le tri de shell, je comprends le
fonctionnementde ce tri mais je n'arrive pas aller jusqu'au bout avec
ce code :

void PERMUTER(int *A, int *B);

/* Variables locales */

int SAUT, M, K;
int TERMINE;

/* Traitements */

SAUT = N;
while (SAUT>1)
{
SAUT /= 2;
do
{
TERMINE=1;
for (M=0; M<N-SAUT; M++) /* Attention aux indices! */
{
K=M+SAUT;
if (*(T+M) > *(T+K))
{
PERMUTER(T+M,T+K);
TERMINE=0;
}
}
}
while(!TERMINE); /* Attention: utiliser la négation de */
} /* la condition employée en lang algorithmique */
}

origine du code :
http://www.ltam.lu/cours-c/
d) Tris de tableaux
Exercice 10.17 Tri de Shell

Je suis bloqué avec while ( saut > 1 ).
Pour un simple tableau avec 6 valeurs numériques :
n = 6 ;
saut = n / 2 = 3
m < n - saut ou m < 3

à la fin de l'iteration (m = 0 k = 3), (m = 1 k = 4), (m = 2 k =
= 6) ;

je comprends que je quitte la boucle do {} while ( !termine ) ;
pour me retrouver dans : while ( saut > 1 ) { et saut /= 2 ;

Mais comme la variable saut contient 3 puisque n = 6 , le code
devrait s'arreter à cet endroit au lieu de continuer avec (m = 0 k =
2), (m = 1 k = 3), (m = 2 k = 5) pour finir avec le tri de shell et
continuer par la suite avec un tri normal m, m+1.

Il existe de nombreuses versions de cet algorithmes plus ou moins
facile à comprendre, comme je considère ce tutoriel suffisant pour mon
niveau, je ne vois pas l'utilité d'appliquer un autre code peut-être
plus performant

Merci,

Pascal
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-marc
Le #21085761
wrote:
Bonjour,



Je suis actuellement "coincé" sur le tri de shell, je comprends le
fonctionnementde ce tri mais je n'arrive pas aller jusqu'au bout avec
ce code :



<snip>

Je suis bloqué avec while ( saut > 1 ).
Pour un simple tableau avec 6 valeurs numériques :
n = 6 ;
saut = n / 2 = 3
m < n - saut ou m < 3
à la fin de l'iteration (m = 0 k = 3), (m = 1 k = 4), (m = 2 k = 6) ;
je comprends que je quitte la boucle do {...} while ( !termine ) ;
pour me retrouver dans : while ( saut > 1 ) { ... et saut /= 2 ;
Mais comme la variable saut contient 3 puisque n = 6 ..., le code
devrait s'arreter à cet endroit au lieu de continuer avec (m = 0 k > 2), (m = 1 k = 3), (m = 2 k = 5)



Tu as loupé une étape.


pour finir avec le tri de shell et
continuer par la suite avec un tri normal m, m+1.



De quoi parles tu?? Il n'y a pas de fin de "tri de shell" pour passer
à un "tri normal" ?



Bref, si tu ne comprends pas le fonctionnement du code, une bonne
façon de faire est de mettre des traces un peu partout et de faire afficher
tes
variables.

Voici ce que ça donne, par exemple :

void tri_shell(int *t, int n)
{
int saut, m, k, termine;

printf("DEBUT fonction.n");
saut = n;
printf("[Avant Premier While] saut = %dn", saut);
while(saut>1)
{
printf(" [Dans while avant division] saut = %dn", saut);
saut /= 2;
printf(" [Danswhile apres division] saut = %dn", saut);
do
{
printf(" [dans do, entree] saut = %dn", saut);
termine = 1;
for(m=0; m<(n-saut); m++)
{
k = m + saut;
if( *(t+m) > *(t+k) )
{
permuter(t+m, t+k);
printf(" [Dans For, PERMUT] [m=%d, k=%d]n", m,k);
termine = 0;
}
}
printf(" [Dans do, avant test sortie] termine = %dn",
termine);
}while(!termine);
printf(" [Apres do]n");
}
printf(" [Apres Premier While]n");
printf("FIN fonction.n");
}


Si maitenant tu remplis un table de 6 éléments avec des valeurs
décroissantes (6,5,4,3,2,1) par exemple, la sortie ressemblera à ceci :

DEBUT fonction.
[Avant Premier While] saut = 6
[Dans while avant division] saut = 6
[Danswhile apres division] saut = 3
[dans do, entree] saut = 3
[Dans For, PERMUT] [m=0, k=3]
[Dans For, PERMUT] [m=1, k=4]
[Dans For, PERMUT] [m=2, k=5]
[Dans do, avant test sortie] termine = 0
[dans do, entree] saut = 3
[Dans do, avant test sortie] termine = 1
[Apres do]
[Dans while avant division] saut = 3
[Danswhile apres division] saut = 1
[dans do, entree] saut = 1
[Dans For, PERMUT] [m=0, k=1]
[Dans For, PERMUT] [m=1, k=2]
[Dans For, PERMUT] [m=3, k=4]
[Dans For, PERMUT] [m=4, k=5]
[Dans do, avant test sortie] termine = 0
[dans do, entree] saut = 1
[Dans For, PERMUT] [m=0, k=1]
[Dans For, PERMUT] [m=3, k=4]
[Dans do, avant test sortie] termine = 0
[dans do, entree] saut = 1
[Dans do, avant test sortie] termine = 1
[Apres do]
[Apres Premier While]
FIN fonction.

1) Si tu ne comprends toujours pas, il suffit d'ajouter des traces.
2) Si ce ne va toujours pas, retourner en 1)

Bonne suite !

Cordialement,

--
Jean-marc
bpascal123
Le #21086631
On Jan 29, 7:34 pm, "Jean-marc"
wrote:
> Bonjour,
> Je suis actuellement "coinc " sur le tri de shell, je comprends le
> fonctionnementde ce tri mais je n'arrive pas aller jusqu'au bout avec
> ce code :

<snip>

> Je suis bloqu avec while ( saut > 1 ).
> Pour un simple tableau avec 6 valeurs num riques :
> n = 6 ;
> saut = n / 2 = 3
> m < n - saut ou m < 3
> la fin de l'iteration (m = 0 k = 3), (m = 1 k = 4), (m = 2 k = 6) ;
> je comprends que je quitte la boucle do {...} while ( !termine ) ;
> pour me retrouver dans : while ( saut > 1 ) { ... et saut /= 2 ;
> Mais comme la variable saut contient 3 puisque n = 6 ..., le code
> devrait s'arreter cet endroit au lieu de continuer avec (m = 0 k =
> 2), (m = 1 k = 3), (m = 2 k = 5)

Tu as loup une tape.

> pour finir avec le tri de shell et
> continuer par la suite avec un tri normal m, m+1.

De quoi parles tu?? Il n'y a pas de fin de "tri de shell" pour passer
un "tri normal" ?

Bref, si tu ne comprends pas le fonctionnement du code, une bonne
fa on de faire est de mettre des traces un peu partout et de faire affich er
tes
variables.

Voici ce que a donne, par exemple :

void tri_shell(int *t, int n)
{
int saut, m, k, termine;

   printf("DEBUT fonction.n");
   saut = n;
   printf("[Avant Premier While] saut = %dn", saut);
   while(saut>1)
   {
      printf("    [Dans while avant division] saut = %dn", s aut);
      saut /= 2;
      printf("    [Danswhile apres division] saut = %dn", sa ut);
      do
      {
         printf("        [dans do, entree] saut = %d n", saut);
         termine = 1;
         for(m=0; m<(n-saut); m++)
         {
            k = m + saut;
            if( *(t+m) > *(t+k) )
            {
               permuter(t+m, t+k);
               printf("            [Dans For, PERMUT] [m=%d, k=%d]n", m,k);
               termine = 0;
            }
         }
         printf("        [Dans do, avant test sortie] t ermine = %dn",
termine);
      }while(!termine);
      printf("        [Apres do]n");
   }
   printf("    [Apres Premier While]n");
   printf("FIN fonction.n");

}

Si maitenant tu remplis un table de 6 l ments avec des valeurs
d croissantes (6,5,4,3,2,1) par exemple, la sortie ressemblera ceci :

DEBUT fonction.
[Avant Premier While] saut = 6
    [Dans while avant division] saut = 6
    [Danswhile apres division] saut = 3
        [dans do, entree] saut = 3
            [Dans For, PERMUT] [m=0, k=3]
            [Dans For, PERMUT] [m=1, k=4]
            [Dans For, PERMUT] [m=2, k=5]
        [Dans do, avant test sortie] termine = 0
        [dans do, entree] saut = 3
        [Dans do, avant test sortie] termine = 1
        [Apres do]
    [Dans while avant division] saut = 3
    [Danswhile apres division] saut = 1
        [dans do, entree] saut = 1
            [Dans For, PERMUT] [m=0, k=1]
            [Dans For, PERMUT] [m=1, k=2]
            [Dans For, PERMUT] [m=3, k=4]
            [Dans For, PERMUT] [m=4, k=5]
        [Dans do, avant test sortie] termine = 0
        [dans do, entree] saut = 1
            [Dans For, PERMUT] [m=0, k=1]
            [Dans For, PERMUT] [m=3, k=4]
        [Dans do, avant test sortie] termine = 0
        [dans do, entree] saut = 1
        [Dans do, avant test sortie] termine = 1
        [Apres do]
    [Apres Premier While]
FIN fonction.

1) Si tu ne comprends toujours pas, il suffit d'ajouter des traces.
2) Si ce ne va toujours pas, retourner en 1)

Bonne suite !

Cordialement,

--
Jean-marc



Bonsoir,

Merci, je comprends.

Je m'étais mal expliqué, mais avec l'explication, j'ai pu mieux
comprendre l'itération et l'ensemble du code. C'est juste que je
trouve les combinaisons des boucles imbriquées while (...) { ... do
{ ... } while (...) ; } moins évidente que les boucles for.
Enfin ça relève des bases de l'algorithme mais avec ta réponse Jean-
marc, j'ai pu voir comment insérer des traces dans le code pour
comprendre.

Merci,

Pascal
Samuel Devulder
Le #21086751
a écrit :

Je suis bloqué avec while ( saut > 1 ).
Pour un simple tableau avec 6 valeurs numériques :
n = 6 ;
saut = n / 2 = 3
m < n - saut ou m < 3

à la fin de l'iteration (m = 0 k = 3), (m = 1 k = 4), (m = 2 k = 6) ;

je comprends que je quitte la boucle do {...} while ( !termine ) ;




Quand tu dis je comprends, tu veux dire quoi? Qu'on sort automatiquement
de ce do-while après la 1er passe? En fait non..

Ce qu'il faut comprendre ici, c'est qu'on sort de la boucle
do-while(!termine) uniquement lorsqu'on a permuté personne, c'est à dire
quand t[0] <= t[saut], t[1] <= t[saut+1], ..., t[n-1-saut]<=t[n-1]. En
gros, le tableau lu de "saut" en saut" est grossièrement trié:

t[0]<= t[saut]<= t[2*saut]<=..<= t[p*saut]
t[1]<=t[1+saut]<=t[1+2*saut]<=..<=t[1+p*saut]
t[2]<=t[2+saut]<=t[2+2*saut]<=..<=t[2+p*saut]
..
t[r]<=t[r+saut]<=t[r+2*saut]<=..<=t[r+p*saut]

avec p = (n-1)/saut, et r = (n-1)%saut (donc r+p*saut==n-1)

La passe suivante se fait en affinant le saut (division par 2), et ainsi
de suite, jusqu'à avoir saut == 1.

Pourquoi 1 forcément au bout? Et bien l'autre jour tu disais que la
numération binaire ne servait pas.. et bien si justement dans ce cas là
par exemple. De la même façon qu'en base 10 quand on divise
successivement par dix, on décale le nombre à droite plusieurs fois
jusqu'à trouver le chiffre le plus significatif (entre 1 et 9 donc), en
binaire, quand on divise par 2, on décale aussi le nombre à droite. En
répétant l'opération, on termine par l'un des chiffres non nul de cette
base et coup de bol, en base 2 le seul chiffre non nul est 1. Donc bref,
tout ceci explique que si on divise un nombre (non nul) par 2 plusieurs
fois, la dernière valeur non nulle trouvée vaut forcément 1! (c'est une
trivialité en fait.. mais je voulais insisté sur le fait que comprendre
la notion de base sert aussi pas mal en informatique).

pour me retrouver dans : while ( saut > 1 ) { ... et saut /= 2 ;

Mais comme la variable saut contient 3 puisque n = 6 ..., le code
devrait s'arreter à cet endroit au lieu de continuer avec (m = 0 k


Pourquoi s'arrêter avec saut==3? je ne vois pas ce qui te permet de
t'arrêter avec un saut qui ne vaut pas 1. On s'arrête quand saut==1 et
que termine==1, et dans ce cas, ca veut dire que
t[0]<=t[1]<=t[2]<=..t[n-1] et que donc le tableau est forcément trié
quand on sort de toutes ses boucles!

Il existe de nombreuses versions de cet algorithmes plus ou moins
facile à comprendre, comme je considère ce tutoriel suffisant pour mon
niveau, je ne vois pas l'utilité d'appliquer un autre code peut-être
plus performant...



L'explication de la wiki est simple.
http://fr.wikipedia.org/wiki/Tri_de_Shell

(une autre explication: http://www.dailly.info/Tri-shell)

Apparemment les seules bonnes optims résident dans le choix des valeurs
de saut. Contrairement à ton implémentation qui prend n/2, n/4, n/8, ..
1 il est empiriquement considéré meilleur de prendre 701, 301, 132, 57,
23, 10, 4, 1 (en fait une suite géométrique de raison 2.3).

Personnellement, je trouve l'implémentation C donnée dans la wiki bien
plus claire à suivre que la tienne. En fait il y a quelque temps tu te
demandais à quoi sert une fonction, et bien dans le code de la wiki cela
permet de mieux suivre l'algo.

En effet, l'équivalent de la boucle do-while(!termine) est séparé dans
une fonction propre avec un commentaire disant précisément ce quelle
fait. Pour le coup la fonction réalise un traitement unique bien
identifié et utilisant son jeu de variables locales à elle.

Le découpage "un traitement autonome==une fonction" permet d'avoir un
code avec moins de dépendances, et qui est donc plus facile à lire et
comprendre.

Pour résumer, un code tel que le tiens avec 3 niveaux de boucles
imbriquées (ou plus) les unes dans les autres est assez dure à lire. Il
est préférable d'introduire une fonction si l'un des traitements interne
le permet.

sam.
bpascal123
Le #21086971
> > pour me retrouver dans : while ( saut > 1 ) { ... et saut /= 2 ;

> Mais comme la variable saut contient 3 puisque n = 6 ..., le code
> devrait s'arreter à cet endroit au lieu de continuer avec (m = 0 k =


***
Pourquoi s'arrêter avec saut==3? je ne vois pas ce qui te permet de
t'arrêter avec un saut qui ne vaut pas 1. On s'arrête quand saut==1
et
que termine==1, et dans ce cas, ca veut dire que
t[0]<=t[1]<=t[2]<=..t[n-1] et que donc le tableau est forcément tri é
quand on sort de toutes ses boucles!
***
Je n'ai pas été au bout de mon problème dans le premier post :

n = 6 et saut = 3 à mes yeux, la boucle devait s'arrêter avec saut = 3
car plus loin ça devient 3 / 2 = 1 (valeur entière) et saut n'est plu s
strictement plus grand que 1 pour continuer avec while ( saut >
1 ) .... c'était sans l'explication de Jean-marc qui m' permit de voir
que j'avais manqué une étape dans l'itération.

Et je maintiens ce que je dis plus haut : je trouve les boucles
imbriquées while (...) { ... do
{ ... } while (...) ; } moins évidentes que les boucles for...

Voici le même algorithme d'un autre site que je trouve plus évident
mais je préfèrre le style du premier code que je trouve plus élégan t,
c'est pourquoi j'ai cherché à comprendre :

void shellsort(int a[],int n)
{
int j,i,k,m,mid;

for(m = n/2 ; m>0 ; m/=2)
{
for(j = m ; j< n ; j++)
{
for(i=j-m ; i>=0 ; i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
mid = a[i];
a[i] = a[i+m];
a[i+m] = mid;
}
}
}
}
}

Merci,

Pascal
Samuel Devulder
Le #21087421
a écrit :

Et je maintiens ce que je dis plus haut : je trouve les boucles
imbriquées while (...) { ... do
{ ... } while (...) ; } moins évidentes que les boucles for...



Ben non, ca change pas grand chose. Ca se lit comme ca s'écrit:
"repète .. tant que(...)". Bref on boucle tout le temps et on sort
naturellement quand le test du while échoue. Le test est effectué à la
fin de la boucle contrairement au while() {} ou au for() {}.

Ce genre de boucles est souvent plus naturel quand le test porte sur un
truc qui est modifié dans le corps de la boucle. On évite une
initialisation qui parait un peu artificielle.

Compares par exemple:
int ok = 1;
while(ok) {
code();
ok = foo();
}
avec
do {
code(); ..
} while(foo());

Tu ne trouves pas la 2eme écriture plus simple et plus logique? En tout
cas elle se lit plus naturellement que la 1ere écriture qui nécessite de
réfléchir au sens de la variable "ok".


Voici le même algorithme d'un autre site que je trouve plus évident



Evident? Vraiment? Pour moi il est plus obscure.

mais je préfèrre le style du premier code que je trouve plus élégant,
c'est pourquoi j'ai cherché à comprendre :

void shellsort(int a[],int n)
{
int j,i,k,m,mid;

for(m = n/2 ; m>0 ; m/=2)
{
for(j = m ; j< n ; j++)
{
for(i=j-m ; i>=0 ; i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
mid = a[i];
a[i] = a[i+m];
a[i+m] = mid;
}
}
}
}
}



J'ai l'impression que ce n'est pas /strictement/ le même algorithme. La
boucle interne itère le tableau en sens inverse (oui bon.. pas grave) et
je soupçonne que celui là fait moins de comparaisons que la version avec
le do..while(!termine) (à cause du break). Mais c'est pas certain.

Par ailleurs j'aime pas ce break qui coupe la logique du code. Il me
semble la boucle interne serait plus lisible ainsi:
for(i=j-m; i>=0 && a[i]>a[i+m]; i-=m) permuter(&a[i],&a[i+m]);

Mais bon c'est plus une affaire de gout que de codage. En tout cas pour
moi, l'état du tableau à la sortie de cet algo là me semble moins
évident qu'avec le do..while(!termine). Comme quoi..

sam.
Publicité
Poster une réponse
Anonyme