Probleme tri fusion

Version imprimable

Probleme tri fusion

Bonsoir, je suis en train de programmer l'algorithme de tri fusion en C et je me casse les dents sur un problème que je n'arrive pas à régler. J'ai deux fonctions recursives : une pour fusionner deux tableaux triés en un seul tableau et l'autre qui est l'algorithme de tri fusion à proprement parler. La fonction "fusion de deux tableaux triés" fonctionne mais impossible de l'utiliser pour faire marcher le triFusion.
Voila mes fonctions :

Code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "fonctions.h"
 
 
void  mkCopy ( int *tab ,int *copie , int size ){
	for (int i =0; i< size ; i++){
		copie[i]=tab[i];
	}
}
 
 
 
void fusion ( int *tab , int *copie , int debut , int x , int milieu , int y , int fin , int incr ){
	if (x == milieu){		
 
		for (int i = debut ; i<=fin ; i++ ){
			printf ( "%d\t" ,  tab[i] ); 
		}
		printf ( "\n\n");
		return;	
	}
	if (y == fin+1 ){
 
		for (int i =0; i < milieu-x ; i++){
			tab[ debut + incr + i] = copie [x+i];
		}
 
		for (int i = debut   ; i<=fin ; i++ ){
			printf ( "%d\t" ,  tab[i] );
		}
		printf ( "\n\n");
		return; 
	}
	if (copie[x]<copie[y]){
		tab [ debut + incr ]=copie[x];	
		fusion ( tab , copie , debut , x+1 ,milieu , y , fin  , incr+1);
	}
 
	if ( copie [y]<= copie[x]){
		tab[debut+incr]=copie[y];
		fusion ( tab , copie , debut , x , milieu , y+1 , fin , incr +1 );
      	} 
}	
 
 
 
void triFusion ( int *tab , int debut , int fin , int size){
	int *copie=malloc(sizeof(int)*size);
	mkCopy ( tab , copie , size );	
	triFusionAux ( tab , copie , debut , fin );
	return;
}
 
 
void triFusionAux ( int *tab , int *copie , int debut , int fin ){
	if ( debut < fin ){
		int milieu = (debut+fin)/2;
		triFusionAux ( tab, copie, debut, milieu);
		triFusionAux (tab , copie , milieu + 1 , fin);
		printf ( "Debut = %d\t, milieu=%d\t, fin=%d\t\t", debut , milieu+1 , fin);
		fusion ( tab ,copie, debut , debut , milieu + 1 , milieu + 1 , fin , 0);
	}
	return;
}

et voila le main :

Code:

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
 
#include <string.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "fonctions.h"
 
 
int main (){
	int copie[5];
	int tib [5]={3,7,2,6,4};
	int tab [5]={2,3,7,4,6};
	triFusion( tib , 0 ,4,5);
	mkCopy ( tab , copie ,5 );
	fusion ( tab , copie , 0 , 0 ,3,3,4,  0);
	for (int i=0 ; i<5;  i++){
	printf ( "%d\t", tib[i]);
	}
	printf ("\n");
	for (int i = 0 ; i<5 ; i++){
		printf  ("%d\t", tab[i]);
	}
	printf("\n");
 
	return 0;
 
}

Les prints placés aux différents endroits affichent des choses que je n'explique pas et que je ne comprends pas 8O. Est-ce quelqu'un peut m'aider svp ?? Merci d'avance.

25/09/2021, 10h13
Sve@r
Bonjour
Une variable remplie dans une fonction est définitivement et irrémédiablement perdue quand la fonction se termine. C'est valable que ce soit pour un simple int...
Code:

1 2 3 void fct() { int n=123; }
... ou bien que ce soit pour un pointeur alloué...
Code:

1 2 3 4 5 void triFusion ( int *tab , int debut , int fin , int size){ int *copie=malloc(sizeof(int)*size); ... return; }
Quant au return final, même s'il ne gêne en rien, sa présence m'incite à me poser des questions sur ce que tu connais de son utilité.
25/09/2021, 12h54
wootwoot
Je ne comprends pas de quel pointeur tu parles.
Pour le tableau copie et bien il ne sert pas en dehors de la fonction triFusion, enfin du moins pas après qu'elle se termine.
Pour le tableau tab, j'ai utilisé le même principe pour faire d'autre algorithme de tri et ca marchait très bien.
Par exemple :
Code:

1 2 void fonctionTri ( int *tab, int size );
Il me semblait aussi que c'était justement à cause de cette spécifité du C que l'on passait des pointeurs aux fonctions. Ou alors il faut que je passe un pointeur de pointeur à une fonction que j'utilise dans une fonction ? Saurais-tu être plus précis ? Merci
25/09/2021, 14h40
wootwoot

J'ai finalement réussi a faire marcher mes fonctions mais seulement en faisant une copie pour chaque appel de fusion alors que j'aurais aimé ne faire qu'une seule copie au moment de l'appel de triFusion. J'imagine que c'est tout a fait possible mais je n'arrive pas à le faire...
25/09/2021, 18h56
Sve@r
Citation:

Envoyé par wootwoot

Je ne comprends pas de quel pointeur tu parles.

int *copie c'est pas un pointeur ? En plus c'est la seule ligne que je reprends, ligne qui contient le schéma "variable=valeur", schéma que je mets dans mon exemple préalable. C'est peut-être un indice non ???

Citation:

Envoyé par wootwoot

Pour le tableau copie et bien il ne sert pas en dehors de la fonction triFusion, enfin du moins pas après qu'elle se termine. i

Ok là c'est un argument valable. Enfin presque car un pointeur alloué doit être libéré quand on n'en a plus besoin. Tu aurais écrit l'instruction de libération je ne me serais pas posé de question sur son devenir quand la fonction se termine.

Citation:

Envoyé par wootwoot

Il me semblait aussi que c'était justement à cause de cette spécifité du C que l'on passait des pointeurs aux fonctions. Ou alors il faut que je passe un pointeur de pointeur à une fonction que j'utilise dans une fonction ? Saurais-tu être plus précis ? Merci

C'est pas tout à fait pour cette raison qu'on utilise les pointeurs. Enfin si ça influe mais ce n'est pas la raison principale. La raison principale des pointeurs en C c'est parce que toute variable passée à une fonction n'est passée que par copie. Donc si la fonction modifie la copie ça ne change rien sur la variable d'origine.
Exemple
Code:

1 2 3 4 5 6 7 8 9 10 int main() { int n=123; printf("n=%d\n", n); fct(n); printf("n=%d\n", n); } void fct(int n) { n=456; }
Malgré le nom identique, les variables ne sont pas les mêmes et la "copie" ne change rien à l'original => on obtient 123 dans les deux cas.

Fort heureusement (et c'est un second point important) la mémoire est unique pour un programme. Donc quand "fct()" tourne, la variable "n" du main est présente quelque part. Et si fct() connait son emplacement, elle a alors la possibilité dy aller la modifier. Donc pour que fct() connaisse cet emplacement (adresse) il suffit de la lui passer.
Code:

1 2 3 4 5 6 int main() { int n=123; printf("n=%d\n", n); fct(&n); printf("n=%d\n", n); }
Et du côté "fct()" elle devra alors stocker cette adresse reçue or le type en C adapté au stockage des adresses est un pointeur.
Ainsi ayant l'adresse de "n" elle a alors possibilité d'y aller modifier son contenu.
Code:

1 2 3 void fct(int *pt) { (*pt)=456; }
Là on aura bien 123 puis 456

Partant de là, le principe est super simple: si une fonction doit modifier une variable de type "truc" en provenance de l'appelant, elle devra s'attendre alors à recevoir l'adresse de cette variable, adresse qu'elle devra stocker dans un "truc étoile" (juste rajouter "étoile" après le type "truc"). Et dans la fonction, tous les accès à ladite variable de l'appelant se feront au travers de etoile pt ("pt" étant le nom de la variable interne ayant reçue ladite adresse).

Tu as parlé de pointeur de pointeur et effectivement ça peut être le cas. Si en effet le type "truc" est déjà lui-même un pointeur (il y a déjà une étoile dans son type) alors son adresse sera effectivement un pointeur de pointeur (on rajoute quand-même l'étoile dans la fonction car c'est systématique: variable de type "truc" => pointeur de type "truc étoile").

Exemple
Code:

1 2 3 4 5 6 7 8 9 10 11 int main() { char *mot; fct(&mot); printf("mot=%s\n", mot); free(mot); } void fct(char **pt) { (*pt)=malloc(10 * sizeof(**pt)); strcpy(*pt, "Hello"); }
Ici le type "truc" est un "char étoile" donc son adresse est un "char étoile étoile". Et si "truc" est un "char étoile étoile étoile" alors "adresse truc" sera un "char étoile étoile étoile étoile". Toujours rajouter une étoile quand on parle de l'adresse de quelque chose. Bon généralement on essaye de ne pas arriver à des cas qui nécessitent plus de deux étoiles (si par exemple on a un "truc étoile étoile étoile" alors on l'encapsule dans une structure et on passe ensuite par l'adresse de cette structure qui, elle, ne contient qu'une étoile).