Discussion :

[DeathMixer]

Bonjour à tous,

Je commence vraiment à desespérer, c'est pour ça que je me tourne vers vous...

Ce que je cherche à faire (comme précisé dans le titre..) c'est trier une table à 2 colonnes en fonctions des valeurs de la première. Je sais que ca peut se faire en C++, mais ce dont j'ai besoin c'est en C

J'ai effectué des recherches, et j'ai découvert la fonction 'qsort', et ce qui m'arrive avec est pour le moins bizarre...

Je m'explique :

Le code suivant fonctionne très bien

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
 
 int tab[4][2] = { 4, 6, -3, 4, 7, 8, -8, -16 };
 
   qsort (tab, sizeof(tab)/sizeof(*tab), sizeof(*tab), compare);
 
	for(i=0; i<4; i++)
	{
		for(j=0; j<2; j++)
			printf("%d ",tab[i][j]);
	}

Avec la fonction 'compare' suivante :

Code :

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

1
2
3
4
5
6
7
8
 
static int compare (const void *a, const void *b){
 
   int pa = * (int*) a;
   int pb = * (int*) b;
 
   return pa - pb;
}

Le problème vient lorsque je l'applique à un tableau plus complexe
(Je vous joints mon bout de code où je l'utilise...)

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
 
int **BuildIndex (int Key, int total, int nbr_word, int doc_nbr, int **D_ronde_w, int *Delta)
{
	int index = 0;							// numero de la ligne de la look_up_table
	int label = 0;							// numero du label
	int i,j;
 
	int **look_up_table = (int**) malloc(total*sizeof(int*));
	for(i=0; i<total; i++)
		*(look_up_table + i) = (int*) malloc(2*sizeof(int));
 
	/* parcours de D(w) pour tout w */
	for(i=0; i<nbr_word; i++)
	{
		for(j=0; j<doc_nbr; j++)
		{
			if(D_ronde_w[i][j] == 1)
			{
				look_up_table[index][0] = ((Delta[i] << 4) + label) ^ Key;
				look_up_table[index][1] = j+1;
				label++;
				index++;
			}
		}
		label = 0;
	}
 
	printf("\nVoici la table de recherche AVANT le tri \n");
	for(i=0; i<total; i++)
		printf(" %X   %X \n ", look_up_table[i][0], look_up_table[i][1]);
 
	qsort(look_up_table, sizeof(look_up_table)/sizeof(*look_up_table), sizeof(*look_up_table), compare);
 
	printf("Voici la table de recherche APRES le tri \n");
	for(i=0; i<total; i++)
		printf(" %X   %X \n ", look_up_table[i][0], look_up_table[i][1]);
 
	return look_up_table;
 
}

Explications :

Je crée d'abord une table de recherche ('look_up_table') en fonction des valeurs de la table 'D_ronde_w' et je crée ensuite des associations Clé/Valeur pour chaque ligne de la table de recherche
... la table de recherche est une table 'total x 2' ...

et le problème est que la table est exactement la même AVANT et APRES le tri !!!!
Je précise quand même que je travaille avec des entiers sur 32 bits (que j'affiche en héxa pour une meilleure visibilité)


Ca fait maintenant 4h que je suis dessus, et je commence un peu à !!!!!!

Merci d'avance pour vos réponses...

PS : je travaille sous Windows, avec Visual Basic 2008 Express. Je n'ai donc pas accès aux fonctions hcreate/hsearch qui créent des tables de hachages bien pratiques... je dois donc me débrouiller avec une table triée et une recherche dichotomique...

PS2 : si ce n'est pas clair, prévenez moi, ou n'hésitez pas à me demander si vous avez besoin de voir le code en entier

[diogene]

Code :

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

1
2
3
int **look_up_table = ...
....
	qsort(look_up_table, sizeof(look_up_table)/sizeof(*look_up_table), sizeof(*look_up_table), compare);

sizeof(look_up_table) donne la taille d'un int** donc la taille d'un pointeur (probablement 4)
sizeof(*look_up_table) donne la taille d'un int* donc la taille d'un pointeur (probablement 4)
ce qui fait que ce code est (probablement) équivalent à

Code :

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

        qsort(look_up_table,1,4, compare);

Il faut explicitement donner le nombre et la taille :

Code :

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

 qsort(look_up_table,total, 2*sizeof(int), compare);

[DeathMixer]

Merci de ta réponse rapide; mais ce que tu dis je l'ai également essayé, et ça me donne exactement le même résultat !!

Mais, normalement, les allocations de mémoire faites en début de programme font que :

Code :

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

sizeof(*look_up_table) vaut 2*sizeof(int)

et

Code :

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

sizeof(look_up_table) vaut total*sizeof(*look_up_table)

Non ??

Enfin, en tout cas, ca me donne exactement le même résultat...

[diogene]

Mais, normalement, les allocations de mémoire faites en début de programme font que :

Code :

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

sizeof(*look_up_table) vaut 2*sizeof(int)

et

Code :

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

sizeof(look_up_table) vaut total*sizeof(*look_up_table)

Non ??

NON. sizeof se base sur le type de l'opérande. look_up_table est défini comme pointeur et sizeof donnera la taille d'un pointeur.
Ce n'est pas pareil que
int tab[4][2]
tab n'est pas un pointeur mais un tableau et sizeof tab donnera 4*2*sizeof(int)

[diogene]

En regardant d'un peu plus près ton code, ceci peut amener la différence :

Code :

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

1
2
3
	int **look_up_table = (int**) malloc(total*sizeof(int*));
	for(i=0; i<total; i++)
		*(look_up_table + i) = (int*) malloc(2*sizeof(int));

En effet, ceci ne construit PAS un tableau d'éléments consécutifs ;

look_up_table[i] est bien un tableau de 2 int consécutifs en mémoire.
Mais ils ne sont PAS consécutifs en mémoire avec ceux de look_up_table[i-1] . -> Tu ne peux faire un qsort sur l'ensemble de tes données.

Il faut impérativement rendre tous ces éléments consécutifs en mémoire, donc allouer tout d'un seul coup (il serait bon de tester le résultat des allocations dynamiques) :

Code :

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

1
2
3
4
 
  int **look_up_table = malloc(total*sizeof(int*));
  look_up_table[0] = malloc(total*2*sizeof(int);
  for(i= 1; i<total; i++)   look_up_table[i] = look_up_table[i-1] +2;

[DeathMixer]

Merci pour cette réponse,
mais je me suis finalament débrouillé autrement :

J'ai en fait déclaré 'look_up_table' comme un tableau à une dimension

Code :

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

1
2
3
4
5
6
 
int *look_up_table = (int*) malloc(2*total*sizeof(int));
 
...
 
qsort(look_up_table,total, 2*sizeof(int), compare);

et ce code là fonctionne très bien et me renvoie le résultat attendu...

[diogene]

C'est ce que le code que j'ai posté construisait en fait si tu l'as lu :

Code :

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

1
2
3
 // int *look_up_table = (int*) malloc(2*total*sizeof(int));
 
//    .......look_up_table[0] = malloc(total*2*sizeof(int));

Les deux autres lignes permettaient de le considérer comme un tableau à deux dimensions comme avant.

Code :

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

1
2
3
4
5
  int **look_up_table = malloc(total*sizeof(int*));
  look_up_table[0] = malloc(total*2*sizeof(int));
  for(i= 1; i<total; i++)   look_up_table[i] = look_up_table[i-1] +2;
  ....
  look_up_table[i][j] = ....