Discussion :

[letopdutop]

Bonjours a tous !

J'ai besoin de développer une fonction de tri par tas générique, voici le .h, le .c et un petit main test :

TasSort.h :

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
 
#ifndef _TASSORT_H_
#define _TASSORT_H_
 
// appel de la fonction de tri par tas, tri suivant Compare, necessite un Swap specifique du type contenu.
void TSort (void* array, int lenght,
	int Compare(void*, int, int), void Swap(void*, int, int));
 
 
 
 
//construit le tas
void construst_tas (void* array, int lenght, 
	int Compare(void*, int, int), void Swap(void*, int, int));
 
//entasse le tas
void entasse (int noeud, void* array, int leght,
	int Compare(void*, int, int), void Swap(void*, int, int));
 
 
#endif

TasSort.c :

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
 
#include "TasSort.h"
 
void TSort (void* array, int lenght,
	int Compare(void*, int, int), void Swap(void*, int, int))
{
	construct_tas (array, lenght, Compare, Swap);
 
	for (int i=lenght-1; i>0; i--) {
		Swap (array, 0, i);
		entasse (0, array, lenght, Compare, Swap);
	}
}
 
 
void construct_tas (void* array, int lenght,
	int Compare(void*, int, int), void Swap(void*, int, int))
{
	for(int i= (lenght/2) - 1; i >= 0; i--)
		entasse (i, array, lenght, Compare, Swap);
}
 
 
void entasse (int noeud, void* array, int lenght,
	int Compare(void*, int, int), void Swap(void*, int, int))
{
	int max = noeud,
		gauche = 2*noeud + 1,
		droite = gauche + 1;
 
	if (gauche < lenght && (Compare(array, gauche, max))) max = gauche;
	if (droite < lenght && (Compare(array, droite, max))) max = droite;
 
	if (max != noeud) {
		Swap (array, noeud, max);
		entasse (max, array, lenght, Compare, Swap);
	}
}
 
// visiblement, il y a des swaps qui ne sont tout bonnement pas pris en compte...

et le main test.c :

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
 
#include "TasSort.h"
#include <stdio.h>
#include <stdlib.h>
 
void intSwap (void* array, int i, int j) {
	int temp = ((int*)array)[i];
	((int*)array)[i] = ((int*)array)[j];
	((int*)array)[j] = temp;	
}
 
void smallest (void* array, int i, int j) {
	return (((int*)array)[i] <= ((int*)array)[j]);
}
 
int main (void) {
 
	int testouille[10] = {2, 4, 2, 6, 8, 3, 3, 12, 1, 0};
 
	TSort(testouille, 10, smallest, intSwap);
 
	printf("\n");
 
	for (int i=0; i<10; i++)
		printf ("%d ", testouille[i]);
 
	printf("\n");
 
	return 0;
}

mon problème ce situe au niveau de la fonction Swap (ligne 6 du main) : appliqué ici, il semble parfois bien fonctionner parfois... n'avoir aucun effet,
du coup a la fin le tableau est trié n'importe comment... j'ai cherché partout la solution, sans succès, est-ce que vous pouvez m'aider à résoudre ce problème ?
Merci pour toute réponse !

[Médinoc]

Pour commencer, tu devrais caster un peu moins, le code n'en serait que plus lisible:

Code :

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

1
2
3
4
5
6
void intSwap (void* pvArray, int i, int j) {
	int *array = pvArray; /*Si tu as besoin d'un cast sur cette ligne, c'est que tu compiles en C++*/
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

Ensuite, pourquoi smallest est-il déclaré avec un retour void? Et pourquoi ton compilo ne gueule-t-il pas quand tu cherches à retourner une valeur depuis une fonction void?

[ternel]

Si tu utilises visual studio, utilise l'option /W3 voire /W4 (maximum de warnings)
Pour un gcc, privilégie -Wall -Wextra

[letopdutop]

Hm effectivement pour le retours void sur la fonction smallest c'est une erreur d'inattention de ma part,
pourquoi le compilateur ne gueule pas ? ca... aucune idée ! ()

Je suis relativement nouveau pour ce qui est de création de programme générique (pour dire c'est la première fois que je manipule des void*) et j'ai tendance a être un peu paranoïaque la dessus pour mes débuts

Je planche la dessus depuis quelques jours et j'arrive vraiment pas a trouver le problème, visiblement même après ca ce programme continue de me le trier n'importe comment, alors que j'implémente a la lettre l'algo du tri par tas de mes cours d'algo, ca pique les nerfs on va dire

[letopdutop]

Ceci étant, après plusieurs test je constate que, après construct_tas j'obtiens bien un tableau qui est un tas, du coup ca doit être l'algorithme de tri
qui doit être faussé quelque part après la construction du tas... une question : dans l'algorithme de mon cours de programmation C, on me dit d'extraire successivement le sommet du tas,
or l'algorithme du tri par tas est un tri sur place normallement, je n'ai pas compris ce point peut être ?

En tout cas le swap semble fonctionner

[letopdutop]

Merci pour vos reponses, j'ai enfin trouvé la solution a mon problème,
qui était un simple oubli de décrementation de la taille du tas après le swap entre le premier et le dernier...
Au moins, ca m'a approté quelques eclaircissement sur la manière de proceder pour les deferencement de tableau sur void !