Un swap deffectueux

Version imprimable

Un swap deffectueux

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:

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:

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:

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 !

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

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?

18/02/2015, 16h57
ternel

Si tu utilises visual studio, utilise l'option /W3 voire /W4 (maximum de warnings)
Pour un gcc, privilégie -Wall -Wextra
18/02/2015, 17h22
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 ! (:aie:)

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 :roll:

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 :(
18/02/2015, 18h12
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
18/02/2015, 18h31
letopdutop

Merci !

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... :roll:
Au moins, ca m'a approté quelques eclaircissement sur la manière de proceder pour les deferencement de tableau sur void ! :mrgreen: