Simple fonction tri qui fonctionne et ne fonctionne pas

Le
bpascal123
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) )
posmin = j ;
Permut(Tab+i, Tab+posmin) ;
}
}

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


ok (ca ne fonctionne pas) :

Nombre de valeurs : 4

SAISIE D'UN TABLEAU
Element[0] : 3

Element[1] : 6

Element[2] : 5

Element[3] : 8


AFFICHAGE DU TABLEAU
3 6 5 8



ok (ca fonctionne pour) :

Nombre de valeurs : 4

SAISIE D'UN TABLEAU
Element[0] : 5

Element[1] : 8

Element[2] : 3

Element[3] : 2

AFFICHAGE DU TABLEAU
2 3 5 8
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
Anthony Gelibert
Le #21109501
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, 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 ;
}


bpascal123
Le #21110151
> 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
-ed-
Le #21110671
On 2 fév, 08:45, ""
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).
Antoine Leca
Le #21110761
é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
bpascal123
Le #21113871
Merci pour toutes ces explications.
-ed-
Le #21116881
On 2 fév, 09:49, -ed-
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 !)
Antoine Leca
Le #21119581
-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
Samuel Devulder
Le #21130171
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.
Samuel Devulder
Le #21130301
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.
Publicité
Poster une réponse
Anonyme