salut,

quand je fais :

int milieu=floor((fin+debut)/2);
int a=floor((fin+debut)/2);
printf("%d\n\n\n",a);

j'obtiens 1 quand je mets fin à 9 et début à 0....
normal ou pas Je dirais que non mais bon...
une explication ?

donne le code complet.

1. include<math.h> oublié?

Si il manquait le include, le compilo le dirait je pense.

void triFusion(int tab[], int debut, int fin)
{
double milieu=floor((fin+debut)/2);
int a=floor((fin+debut)/2);

printf("%d\n\n\n",a);

printf("milieu:%d\n debut:%d\n fin:%d\n calcul du milieu %d\n",milieu, debut, fin, floor((fin+debut)/2)); scanf("%d",&milieu);
if (!(debut==fin)) {
if (abs(fin-debut)==1) {
if (tab[fin]<tab[debut]) echange(tab,debut,fin);
}
else {
triFusion(tab, debut, milieu);
triFusion(tab, milieu+1, fin);
fusion(tab, debut, milieu, milieu+1, fin);
}
}
}

le include est présent je précise.

rien de bien compliqué pourtant, je ne comprends pas... les printf() c'est pour le débuggage bien sur

sd460 : je reviens sur le message initial... on est bien d'accord que 5 / 2 ça renvoie 2 (et donc que c'est complètement inutile d'utiliser floor) ?

"5 / 2 ça renvoie 2"

Seulement si 5 et 2 sont des entiers (je ne sais pas sous quelles conditions la promotions vers des flottants s'effectue lorsque l'un ou l'autre sont flottant). Sinon, (int)(5./2.) n'est pas défini par la norme.

ok je ne savais pas. Enfin je l'ai su, mais c'était loin pour moi
merci c'est bon du coup

dnob700 : dans ce contexte, ce sont des entiers (positifs en plus).
Quant à (int)(5./2.), j'ai envie de dire que float -> int ça se fait à coup de floor, donc ça devrait renvoyer 2. (flemme de tester, tant pis pour moi si j'ai dit nimp... )

puisque je suis dans le C... Pouvez me dire pourquoi j'ai un prb avec mon tableau temp ? Ca plante, dans l'erreur j'ai un prb de stack apparemment....(avec temp)
[comme vous l'avez compris ca intervient dans le tri par fusion, ou j'appelle cette fonction]

void fusion(int tab[], int debut, int milieu, int fin) //fusion de 2 sous-tableaux triés
{
int i,j,k;
int temp[MAX];

for(i=milieu;i<=debut;i--) temp[i]=tab[i];
for(i=milieu+1;i<=fin;i++) temp[debut+milieu+1-i]=tab[i];

i=debut; j=fin;
for(k=debut;k<=fin;k++) {
if (temp[i]<temp[j]) {
tab[k]=temp[i];
i++;
}
else {
tab[k]=temp[j];
j--;
}
}
}

déjà, à vue d'œil,
for(i=milieu;i<=debut;i--) temp[i]=tab[i];

je pense que tu as voulu ecrire ceci:
for ( i = milieu; i > debut; i -- ) temp[i] = tab[i] ;

le problème vient peut être aussi du fait que tu accèdes dans ton parcours à un élément qui n'a pas été initialisé
pour un tableau de MAX éléments, le dernier élément se trouve à l'indice MAX-1, donc si tu boucles sur les indices tu dois t'arrêter à l'élément d'indice MAX-1.
en gros for(i=milieu+1;i<=fin;i++) devient for(i=milieu+1;i<fin;i++)
c'est bête mais c'est souvent source d'erreurs
après ça dépend avec quels paramètres tu appelles ta fonction..

chris : "Quant à (int)(5./2.), j'ai envie de dire que float -> int ça se fait à coup de floor, donc ça devrait renvoyer 2. (flemme de tester, tant pis pour moi si j'ai dit nimp... )"

Non, ce que je voulais dire c'est que ce comportement ne peut pas se tester, car la norme dit qu'un compilo peut utiliser floor, ou round ou nearestint ou ceil, ou ce qu'il vaut du moment que ça valide certaine règle, mais d'un compilo à l'autre ça peut changer.

ah oui pour l'erreur de signe. Mais en fait cela ne change rien, mon tableau est touours "corrupted".

Je l'appelle comme ca :

void triFusion(int tab[], int debut, int fin)
{
int milieu=(fin+debut)/2;

if (!(debut==fin)) {
if (abs(fin-debut)==1) {
if (tab[fin]<tab[debut]) echange(tab,debut,fin);
}
else {
triFusion(tab, debut, milieu);
triFusion(tab, milieu+1, fin);
fusion(tab, debut, milieu, fin);
}
}
}

bon merci, je me suis débrouillé autrement. Le C me revient petit à petit

Pour ce qui est de la complexité de l'algorithme du tri - fusion, j'ai du n*logn, par contre est-ce la compexité au pire ou en moyenne ?

merci

Déjà je trouve que tu nous embrouille tous (y compris toi-même) pour pas grand chose à parcourir une partie du tableau dans un sens et l'autre dans l'autre sens. Mais ce n'est pas ça qui dois empêcher ton prog de marcher.

Par contre je remarque que dans fusion() une fois que i ou j a atteint sa borne tu continue comme si de rien n'était, ça risque pas trop de marcher correctement ça.

Avec le tri fusion pas d'embrouille, c'est à la fois la complexité la pire et la moyenne qui sont en n*log n.

Par contre avec le tri rapide, la complexité moyenne est en n*log n mais il me semble que la complexité la pire est en n*n.

dnob et chris,
Je ne savais pas que la norme C ne disait rien la dessus.(Ce qui veut dire que j'ai un bon paquet de code compilateur depend)
Par contre, la fonction floor prends un float et rend un float. Elle ne fait pas de transformation vers int! Il doit falloir utiliser lrint pour faire la transformation float vers int.
et donc au lieu d'ecrire
float b;
int a = b;
il faudrait ecrire
int a = lrint(floor(b));

Jujudredd, c'est ca!