Simple fonction tri qui fonctionne et ne fonctionne pas

Quelques erreurs dans ton algo de tri.
Ceci devrait fonctionner mieux :

void TriSelect(int *Tab, int dim1)
{
int i, j, posmin;

for (i = 0, posmin = i; i < dim1 - 1; i++,posmin=i)
{
for (j = i + 1; j < dim1; j++)
{
if (*(Tab + posmin) > *(Tab + j))
posmin = j;
}
if (posmin != i)
Permut(Tab + i, Tab + posmin);
}
}

Bonne journée
Anthony Gelibert


On 2010-02-01 20:53:27 +0100, bpascal123@googlemail.com said:

void TriSelect(int *Tab, int dim1)
{
void Permut(int *x, int *y) ;
int i, j, posmin ;

for ( i = 0, posmin = i ; i < dim1-1 ; i++ )
for ( j = i + 1 ; j < dim1 ; j++ )
{
if ( *(Tab + posmin) > *(Tab + j) )
posmin = j ;
Permut(Tab+i, Tab+posmin) ;
}
}

void Permut(int *x, int *y)
{
int aide ;
aide = *x ;
*x = *y ;
*y = aide ;
}

> void TriSelect(int *Tab, int dim1)
{
        int i, j, posmin;

        for (i = 0, posmin = i; i < dim1 - 1; i++,posmin=i)
        {
                for (j = i + 1; j < dim1; j++)
                {
                        if (*(Tab + posmin) > *(T ab + j))
                                posmin = j;
                }
                if (posmin != i)
                        Permut(Tab + i, Tab + pos min);
        }

}

Bonne journée
Anthony Gelibert

Bonjour,

Votre solution fonctionne et en fait, avec j'ai compris quelque
chose :

...

        for (i = 0, posmin = i; i < dim1 - 1; i++,posmin=i)
        {
                for (j = i + 1; j < dim1; j++)

...
est différent de :
...
for ( i = 0 ; i < dim1-1 ; i++ )
{
posmin = i ;
for ( j = i + 1 ; j < dim1 ; j++ )
...

C'est une question de débutant mais apparemment la position de posmin
a des conséquences. Comme paramètre de "For" posmin n'est affecté
qu'une fois en début de boucle ? Comme affectation de variable, posmin
est affecté à chaque fois que i est incrémenté?

Cependant la solution d'Anthony fonctionne et permet de s'assurer que
posmin est bien mis à jour dans la première boucle. J'espère cette
interprétation cohérente.

Merci,
Pascal

On 2 fév, 08:45, "bpascal...@googlemail.com"
<bpascal...@googlemail.com> wrote:

Votre solution fonctionne et en fait, avec j'ai compris quelque
chose :

...>         for (i = 0, posmin = i; i < dim1 - 1; i++,posmin =i)
>         {
>                 for (j = i + 1; j < dim1; j++)

...
est différent de :
...
        for ( i = 0  ;  i < dim1-1  ;  i++ )
        {
                posmin = i  ;
                for ( j = i + 1  ;  j < dim1  ;  j++ )
...

C'est une question de débutant mais apparemment la position de posmin
a des conséquences. Comme paramètre de "For" posmin n'est affecté
qu'une fois en début de boucle ? Comme affectation de variable, posmin
est affecté à chaque fois que i est incrémenté?

Oui, le 3ème membre de la structure de code for() est exécuté après le
corps de la structure. (donc complètement à la fin de la boucle).

bpascal123@googlemail.com écrivit :

for (i = 0, posmin = i; i < dim1 - 1; i++,posmin=i)
{
for (j = i + 1; j < dim1; j++)

...
est différent de :
...
for ( i = 0 ; i < dim1-1 ; i++ )
{
posmin = i ;
for ( j = i + 1 ; j < dim1 ; j++ )
...

Uniquement si tu te places à l'extérieur de la boucle (à la sortie de la
boucle, dans la première version posmin sera supérieur d'une unité).

C'est une question de débutant mais apparemment la position de posmin
a des conséquences.

Oui mas pas ici.
Dans ton code initial l'affectation posmin=i comme 3e élément du for
n'existait pas, et là bien sûr c'est tout-à-fait différent.

Comme paramètre de "For" posmin n'est affecté qu'une fois en début
de boucle ?

Non. En fait quand tu vois des choses un peu bizarres de la forme

for ( expr1 ; expr2 ; expr3 ) {
instrA;
instrB;
}

tu dois le remplacer mentalement par

expr1;
while ( expr2 ) {
instrA;
instrB;
expr3;
}

Autrement dit, « expr1 » est toujours exécuté une seule fois,
« expr2 » est un test qui sera exécuté N+1 fois (si la boucle tourne N
fois), et « expr3 » sera exécuté N fois, donc éventuellement jamais (si
N==0, donc si le test expr2 est faux dès le départ).

[ J'ai simplifié en ne prenant pas en compte break; ]

Si on déroule ensuite la boucle while, on obtient alors

expr1;
if ( ! expr2 ) goto fin;
instrA;
instrB;
expr3;
if ( ! expr2 ) goto fin;
instrA;
instrB;
expr3;
if ( ! expr2 ) goto fin;
instrA;
instrB;
expr3;
if ( ! expr2 ) goto fin;
/* ... */
fin:

Autrement dit, « expr3 » est suivi de « expr2 » et de « instrA » ;
si « expr2 » ne modifie pas une variable i, une affectation posmin=i
sera donc idempotente dans « expr3 » ou dans « instrA », sauf si tu te
places après la fin de la boucle.


Antoine

Merci pour toutes ces explications.

On 2 fév, 09:49, -ed- <emmanuel.delah...@gmail.com> wrote:

Oui, le 3ème membre de la structure de code for() est exécuté apr ès le
corps de la structure. (donc complètement à la fin de la boucle).

En relisant, je constate que ce n'est pas très clair. Voir
l'explication d'Antoine qui est parfaite (comme toujours !)

-ed- écrivit :

explication d'Antoine qui est parfaite (comme toujours !)

Tu dis cela parce que j'ai écrit une bourde il y a deux jours ?
(à propos des conversions de truc * * vers const truc * *,
comme quoi le comportement était indéfini, toussâkwa)
:-)

Antoine

bpascal123@googlemail.com a écrit :

Bjr||bsr,

Cette fonction ci-dessous fonctionne alternativement comme attendue et
ne fonctionne pas. Voici :

void TriSelect(int *Tab, int dim1)
{
void Permut(int *x, int *y) ;
int i, j, posmin ;

for ( i = 0, posmin = i ; i < dim1-1 ; i++ )
for ( j = i + 1 ; j < dim1 ; j++ )
{
if ( *(Tab + posmin) > *(Tab + j) )

Une suggestion: ne préfèrerais tu pas écrire la notation infiniment plus
naturelle type tableau:
if(tab[posmin] > tab[j])

posmin = j ;
Permut(Tab+i, Tab+posmin) ;

Ou: Permut(&Tab[posmin], &Tab[i])

Qui me semble un poil plus clair (passage par adresse des elements qu'on
veut permutter).. mais c'est juste une question de gout.

}
}

sam.

bpascal123@googlemail.com a écrit :

Votre solution fonctionne et en fait, avec j'ai compris quelque
chose :

...

for (i = 0, posmin = i; i < dim1 - 1; i++,posmin=i)
{
for (j = i + 1; j < dim1; j++)

...
est différent de :
...
for ( i = 0 ; i < dim1-1 ; i++ )
{
posmin = i ;
for ( j = i + 1 ; j < dim1 ; j++ )
...

Ben non.. Dans les deux versions, si dim1>1, alors à l'interieur des
boucles posmin a toujours la même valeur aux mêmes instants. Si
dim1<=1, alors il y a une légère différence car posmin ne sera pas
affecté dans la 2eme version, mais cela ne change pas grand chose sur le
fond.

Cependant la solution d'Anthony fonctionne et permet de s'assurer que
posmin est bien mis à jour dans la première boucle. J'espère cette
interprétation cohérente.

Non le gros problème de ta version c'est que du échanges
systématiquement les deux éléments i et posmin inconditionnellement. A
ton avis, que se passe t'il si l'élément i est au final plus petit que
tous les éléments qui suivent (cas d'un tableau partiellement trié)? Ben
ca donne ton résultat: le tableau n'est pas trié.

Dans cet algo on cherche à placer en tab[i] le plus petit élément du
reste du tableau. C'est l'algo du tri a bulle (on fait remonter les
éléments les plus gros comme des bulles). La boucle la plus interne
cherche justement à trouver l'index d'un élément dans le reste du
tableau (ie dans [i+1, dim1[ ) qui est plus petit que l'élément i
lui-même. Si un tel élement est trouvé (i.e. posmin est plus grand que
i), alors on permute, sinon c'est que le tableau est déjà partiellement
trié pour l'élément i et on ne fait rien. C'est l'essence de l'algo
d'anthony.

sam.