Discussion :

[Go'Gaule]

Bonjour à toutes et tous .

J'essaye de me "perfectionner" en c++ car pour moi actuellement c'est plutôt c-- .
J'ai acheté le livre de Brice-Arnaud Guérin et tente de comprendre . (Pas çafile.)
Dans l'introduction il explique : L'utilisation de pointeurs de fonctions pour rendre les algorithmes génériques .
L'algorithme de tri rapide .
La première implémentation donnée , fonctionne . La seconde ne semble pas fonctionner , mais je ne comprend peut-être pas tout .

Avez-vous lu ce livre ? et le pb vient-il du livre ou un manque de compréhension perso ?

Cordialement.

[koala01]

Salut,

Je n'ai pas lu le livre, mais si, dans l'introduction, il parle déjà de générique et de pointeurs de fonctions, argh...kheuf... kheuf... hummm... bon, je vais rester gentil car, ou bien il s'adresse déjà à des débutants avancés, ou bien on peut peut vraiment remettre en cause la qualité du bouquin (tout dépend en fait de comment il implémente la chose )

Sinon,Le gros problème, lorsque l'on parle d'un bouquin sur le forum, c'est qu'il faut partir du principe que peu de gens l'ont lu, et que personne ne sera d'accord pour l'acheter "rien que pour le plaisir de t'aider"

Comme je ne doute absolument pas que la réponse est importante pour toi, je te conseillerais donc de nous fournir un minimum nous permettant de t'aider sans avoir besoin du bouquin, à savoir... le code des deux implémentations (celle qui fonctionne et celle qui ne fonctionne pas).

De cette manière, nous pourrons te dire si tu es passé à coté de quelque chose ou si c'est une erreur dans le bouquin

[Go'Gaule]

Bonjour à toutes et tous .

@koala01 Merci pour ta réponse .

Je n'ai pas posté de code pour ne pas sur-charger mon message .

Si je me fie à ta réaction , mon achat n'est pas top .

Le code qui fonctionne , a savoir la liste est triée .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
69
70
71
 
#include <CoreFoundation/CoreFoundation.h>
 
 
int partition (int* T,int m, int d) {
	int v , aux;
	//int m1=m, d1=d;
 
	v=T[m+(d-m)/2];
	while(m<d)
	{
		while(m<d && T[d]>v)
			d--;
		while(m<d && T[m]<v)
			m++;
		if (m>=d)
			break;
		if (T[m] != T[d])
		{ // échange
			aux=T[d];
			T[d]=T[m];
			T[m]=aux;
		}
		else 
			d--;
	}
	return m;
 
}
void tri_aux(int* T,int m,int d)
{
	if(m>=d)
		return;
	int k=partition(T,m,d); // partitionne entre m et d
	tri_aux(T,m,k-1); // tri à gauche
	tri_aux(T,k+1,d); // tri à droite
}
void tri(int* T,int length)
{
	tri_aux(T,0,length-1);
}
void afficher(int T[], int m, int d)
{ 
	// affichage du tableau à chaque étape
	for(int i=m; i<=d; i++)
		printf("%d,",T[i]);
	printf("\n");
}
void int_echange(void*t,int p1, int p2)
{
	int*T=(int*)t; // transtypage (cast)
	int aux=T[p1];
	T[p1]=T[p2];
	T[p2]=aux;
}
int int_compare(void*t, int p1, int p2)
{
	int v1,v2;
	int*T=(int*)t; // transtypage (cast)
		   v1=(int) T[p1];
		   v2=(int) T[p2];
 
		   return v1-v2;
		   }
int main()
{
	int tab[]={5,1,7,2,8,4,9,13};
	tri (tab,8);
	afficher (tab,0,7);
	return 0;
}

Le code qui ne fonctionne pas :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
69
70
71
72
73
74
75
76
77
78
79
80
#include <CoreFoundation/CoreFoundation.h>
 
typedef void (*pf_echange)(void* , int,int);
typedef int (*pf_comp) (void* , int, int);
 
int partition (void* T,int m, int d ,pf_echange fswap, pf_comp fcomp) 
{   // valeur pivot , variable d'echange
 
	int pv ;
	int m1=m, d1=d;
	// initialisation
 
	pv=m+(d-m)/2; // position du pivot
 
	// tant que les index ne se croisent pas 
	while(m<d)
	{ 
		// rechercher une valeur inférieur à droite 
		while(m<d && (*fcomp)(T,d,pv)>0)
			d--;
		// rechercher une valeur inférieur à gauche
		while(m<d && (*fcomp)(T,m,pv)<0)
			m++;
 
		if (m>=d)
			break;
 
		if ((*fcomp)(T,m,d) !=0)
		{ // échange
			(*fswap)(T,m,d);
		}
		else 
			d--;
	}
	return m;
 
}
void tri_aux(int* T,int m,int d,pf_echange fswap, pf_comp fcomp)
{
	if(m>=d)
		return; // rien à trier 
 
	int k=partition(T,m,d,fswap,fcomp); // partitionne entre m et d
	tri_aux(T,m,k-1,fswap,fcomp); // tri à gauche
	tri_aux(T,k+1,d,fswap,fcomp); // tri à droite
}
void tri(int* T,int length, pf_echange fswap, pf_comp fcomp)
{
	tri_aux(T,0,length-1, fswap , fcomp);
}
void afficher(int T[], int m, int d)
{ 
	// affichage du tableau à chaque étape
	for(int i=m; i<=d; i++)
		printf("%d,",T[i]);
	printf("\n");
}
void int_echange(void*t,int p1, int p2)
{
	int*T=(int*)t; // transtypage (cast)
	int aux=T[p1];
	T[p1]=T[p2];
	T[p2]=aux;
}
int int_compare(void*t, int p1, int p2)
{
	int v1,v2;
	int*T=(int*)t; // transtypage (cast)
		   v1=(int) T[p1];
		   v2=(int) T[p2];
 
		   return v1-v2;
		   }
int main()
{
	int tab[]={5,1,7,2,8,4,9,13};
	tri (tab,8, &int_echange,&int_compare);
	afficher (tab,0,7);
	return 0;
}

Cordialement.

[JolyLoic]

Amusant, chez moi, c'est le code qui est sensé marcher qui ne marche pas (Il faut remplacer v1=(int) T(p1); par v1=(int) T[p1]; et idem à la ligne suivante).

Sinon, il est intéressant pour qu'on puisse t'aider d'indiquer ce qui ne marche pas. Ici, le code compile, mais donne un mauvais résultat. Il aurait aussi pu s'agit d'un problème de compilation.

Sur l'erreur de logique en question, dans le premier code, il utilise comme valeur du pivot :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

v=T[m+(d-m)/2];

Dans le second, il ne garde pas en mémoire la valeur du pivot, mais sa position :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

pv=m+(d-m)/2; // position du pivot

Le problème, c'est que comme il réordonne ses valeurs, la valeur placée à la position du pivot ne reste pas stable tout au long de l'algorithme...

Dit autrement, il a démontré comment en utilisant les mauvaises abstractions pour rendre du code générique, on se plante en beauté En particulier, son pointeur de fonction de comparaison pf_comp au lieu de simplement comparer des valeurs compare des éléments situés à certains index d'un tableau. S'il avait utilisé une vraie fonction de comparaison, tout cela ne serait pas arrivé.

Sinon, sur ce que ce bout de code, et le fait qu'il soit en introduction, me dit sur le reste du livre (ce qui est un exercice qui tient un peu de la boule de cristal) :
Ce livre s'adresse aux gens qui ont une bonne connaissance du C et qui veulent passer au C++, et l'auteur est visiblement lui aussi plutôt dans cette situation. En particulier, ce code ne ressemble pas à du code C++ classique, et possède, bug à part, un certain nombre de défauts :
- Typage trop faible des fonctions de configuration de l'algorithme (demandant des cast)
- Choix de pointeurs de fonctions là où des foncteurs seraient préférables
- Utilisation de bibliothèques C pour faire des I/O
- Utilisation de structure bas niveau (tableau) plutôt que de structures haut niveau (vector)

Peut-être la suite du livre revient-elle sur ces défauts pour les corriger un à un, en expliquant à chaque fois les notions de remplacement. Dans ce cas, le livre a probablement de l'intérêt pour des lecteurs ayant une maîtrise préalable du C++. Si ce n'est pas le cas, je déconseillerais ce livre.

[koala01]

Sinon, sur ce que ce bout de code, et le fait qu'il soit en introduction, me dit sur le reste du livre (ce qui est un exercice qui tient un peu de la boule de cristal) :
Ce livre s'adresse aux gens qui ont une bonne connaissance du C et qui veulent passer au C++, et l'auteur est visiblement lui aussi plutôt dans cette situation. En particulier, ce code ne ressemble pas à du code C++ classique

Bienvenue au club...

C'est exactement la réaction que j'ai eue et qui m'a fait m'étouffer à moitié

PS: C'est quelle marque, ta boule de crystal, pour que je puisse comparer avec la mienne :quesiton:

[Go'Gaule]

Bonsoir à toutes et tous .

@JolyLoic , Merci .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Amusant, chez moi, c est le code qui est sensé marcher qui ne marche pas (Il faut remplacer v1=(int) T(p1); par v1=(int) T[p1]; et idem à la ligne suivante).

Pour les crochets c'est une erreur de ma part , j'ai oublié de corriger avant de poster le code .
Donc dans le 1er cas , les nombres sont triés et classés .
Dans le 2eme cas le code compile sans erreur , mais les nombres ne sont pas classés . Le chiffre 4 ce promène .

Cordialement .

[JolyLoic]

As tu lu la suite de ma réponse, qui indique le problème de logique dans le code ?

[Go'Gaule]

Bonjour à toutes et tous .

@JolyLoic , Merci .

J'ai lu et compris tes explications , mais dans le commentaire du livre il n'explique pas cela .

Mon message précédent donnais les explications manquantes .

Cordialement.