Qsort sur un tableau en 2D

**sniperseb** · 26/01/2006, 10h50

Bonjour a tous, voici mon probleme avec le Qsort.

Je dois trier mon tableau 2d seulement sur la deuxieme colonnes, de plus mon tableau est un tableau dynamique.

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
 
int** indice3 = tableau(tablelg,2); // Fonction qui crée dynamiquement un tableau de  "tablelg"ligne et de 2 colonnes.
 
/* Méthode de comparaison, indispensable pour le qsort */
static int compare (void const *a, void const *b) 
{ 
int const *a1 =(int *) a;
int const *b1 =(int *) b;
    if (a1[1] == b1[1]) 
   { return 0;} 
   else if (a1[1]> b1[1]) 
   { 
      return 1; 
   } 
   else 
   { 
      return -1; 
   } 
}
 
// Appelle de la fonction de trie
qsort(*indice3,2*tablelg,2,compare);

le probleme c'est que le resusltat n'est pas du tout ca :s donc je suis un peu bloqué car je vois pas mon problème.

Pour illustrer mon probleme voici ce que je voudrais

10 15
2 6
9 18
5 5

Je voudrais que ca fasse
5 5
2 6
10 15
9 18

Donc voila, qqn pourrait m'aider svp??

**PRomu@ld** · 26/01/2006, 11h34

Dis nous ce que fais ton programme lorsque tu l'exécute ? seg fault ? tableau non trié ?

le man de qsort me sort ceci :

Code :

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

1
2
3
 
qsort (void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))

nmemb : le nombre de case à trier.
size : la taille des éléments.

Or tu donnes ceci :

nmemb = 2*tablelg
size = 2

tablelg, c'est quoi ? Si j'ai bien compris, c'est le nombre de ligne de ton tableau. Et c'est bien ces tablelg lignes que tu veux trier. Par conséquent, nmemb devrait être égal à tablelg.

Ensuite, 2, c'est quoi ? C'est censé être la taille des éléments de ton tableau. (dans ton cas, un élément est une ligne). Par conséquent, cette taille ne me semble pas juste. (utilise un sizeof au moins, parce que deux, c'est surement pas ça).

**sniperseb** · 26/01/2006, 11h53

le tableau n'est pas trié il reste le meme sauf pour la ligne 0 de mon tableau qui est remplacé par un chiffre incompréhensible.

Après, mon tableau indice3[x][y].
x ---> c'est le nombre de lignes,elle a pour valeur tablelg.
y---> Nombre de colonnes, on la limite à 2 colonnes.

Donc tablelg cé le nombre de lignes, donc pour moi le nombre d'element de mon tableau est tablelg*2. (je vais tester tablelg tout court pour voire)

Ensuite , le "2" dans mon qsort cé tout simplement la taille d'un INT. Si je sais bien , c'est deux. Mais bon, je vais mettre sizeof(int).

Je vais tester ce que tu ma dit.
Ca marche toujours pas :'( . VOici ce qu'il met donne :

Veuillez Indiquer le nombre de point : 10
avant le tri
Indice: 0 Angle : 29358
Indice: 1 Angle : 0
Indice: 2 Angle : 37433
Indice: 3 Angle : 36314
Indice: 4 Angle : 39707
Indice: 5 Angle : 50797
Indice: 6 Angle : 15660
Indice: 7 Angle : 91510
Indice: 8 Angle : 137340
Indice: 9 Angle : 28309

apres le tri
Indice: 8924512 Angle : 8924672
Indice: 1 Angle : 0
Indice: 2 Angle : 37433
Indice: 3 Angle : 36314
Indice: 4 Angle : 39707
Indice: 5 Angle : 50797
Indice: 6 Angle : 15660
Indice: 7 Angle : 91510
Indice: 8 Angle : 137340
Indice: 9 Angle : 28309
Press any key to continue

Voici ce que j'ai remplacé

Code :

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

qsort(*indice3,tablelg,sizeof(int),compare);

La méthode compare n'a pas été modifié.

**PRomu@ld** · 26/01/2006, 12h02

Ensuite , le "2" dans mon qsort cé tout simplement la taille d'un INT. Si je sais bien , c'est deux. Mais bon, je vais mettre sizeof(int).

Un int n'est pas sur 2 octets ... . De plus dans ton cas, c'est la taille d'une ligne qu'il te faut et pas la taille d'une case.

**sniperseb** · 26/01/2006, 12h12

J'ai fait la modification pour le qsort pour mettre la taille dela ligne..mais c'est pire ...

Code :

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

qsort(*indice3,tablelg,2*sizeof(int),compare);

Il me donne ca comme résultat :

Veuillez Indiquer le nombre de point : 10
avant le tri
Indice: 0 Angle : 18534
Indice: 1 Angle : 66104
Indice: 2 Angle : 114010
Indice: 3 Angle : 16514
Indice: 4 Angle : 93576
Indice: 5 Angle : 61916
Indice: 6 Angle : 12750
Indice: 7 Angle : 35563
Indice: 8 Angle : 63993
Indice: 9 Angle : 13432
apres le tri
Indice: 88 Angle : -33686019
Indice: 1 Angle : 66104
Indice: 8924736 Angle : 8924576
Indice: 8924576 Angle : 8924448
Indice: 4 Angle : 93576
Indice: 5 Angle : 61916
Indice: 6 Angle : 12750
Indice: 7 Angle : 35563
Indice: 8 Angle : 63993
Indice: 9 Angle : 13432
Press any key to continue

Ce n'est pas ma méthode compare qui cause ceci?

**Emmanuel Delahaye** · 26/01/2006, 14h38

Envoyé par sniperseb

Bonjour a tous, voici mon probleme avec le Qsort.
<...>
Donc voila, qqn pourrait m'aider svp??

Il faut lire la doc de qsort() plus sérieusement,

http://man.developpez.com/man3/qsort.3.php

et soigner ses identificateurs. Le code doit se lire comme un livre...

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include <stdlib.h>
#include <stdio.h>
 
/* 0 | 1 */
#define DBG 0
 
#if DBG
static void display_line (char const *s, int* p, int nb_col)
{
   int j;
 
   printf ("%s: ", s);
   for (j = 0; j < nb_col; j++)
   {
      printf ("%-3d", p[j]);
   }
   printf ("\n");
}
#endif
 
/* Fonction de comparaison pour qsort() */
static int compare (void const *a, void const *b)
{
   /* -ed-
      Le tableau a trier a des elements de type int *
      On recoit l'adresse de l'element de type int*, soit int **
   */
   int const **ppa = a;
   int const **ppb = b;
 
   /* -ed- on recupere l'adresse de la ligne  */
   int const *pa = *ppa;
   int const *pb = *ppb;
 
#if DBG
 
   display_line("pa", pa, 2);
   display_line("pb", pb, 2);
#endif
 
   /* -ed- on teste la colonne 1 */
   return pa[1] - pb[1];
}
 
/* -ed- creation dynamique du tableau */
static int** create(int nb_lin, int nb_col)
{
   int **pp = malloc (sizeof * pp * nb_lin);
 
   if (pp != NULL)
   {
      int i;
      for (i = 0; i < nb_lin; i++)
      {
         pp[i] = malloc (sizeof * pp[i] * nb_col);
      }
   }
   return pp;
}
 
/* -ed- creation dynamique du tableau */
static void delete(int**pp, int nb_lin)
{
   if (pp != NULL)
   {
      int i;
      for (i = 0; i < nb_lin; i++)
      {
         free (pp[i]), pp[i] = NULL;
      }
   }
   free (pp), pp = NULL;
}
 
static void display (int** pp, int nb_lin, int nb_col)
{
   int i;
   for (i = 0; i < nb_lin; i++)
   {
      int j;
      for (j = 0; j < nb_col; j++)
      {
         printf ("%3d", pp[i][j]);
      }
      printf ("\n");
   }
}
 
int main (void)
{
   int nb_lin = 4;
   int nb_col = 2;
   int** tab2D = create (nb_lin, nb_col);
 
   tab2D[0][0] = 10 ;
   tab2D[0][1] = 15;
 
   tab2D[1][0] = 2 ;
   tab2D[1][1] = 6;
 
   tab2D[2][0] = 9 ;
   tab2D[2][1] = 18;
 
   tab2D[3][0] = 5 ;
   tab2D[3][1] = 5;
 
   display (tab2D, nb_lin, nb_col);
 
   // Appel de la fonction de tri
   {
      /* -ed- verifier que l'on passe les bons parametres */
      size_t nb_membres = nb_lin;
      size_t sz_membre = sizeof * tab2D;
      printf ("nb = %u sz = %u\n", (unsigned) nb_membres , (unsigned) sz_membre);
 
      qsort (tab2D, nb_membres , sz_membre, compare);
   }
 
   display (tab2D, nb_lin, nb_col);
 
   delete (tab2D, nb_lin);
 
   return 0;
}

Ce qui donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
 10 15
  2  6
  9 18
  5  5
nb = 4 sz = 4
  5  5
  2  6
 10 15
  9 18

**sniperseb** · 26/01/2006, 19h38

Je te remercie, il marche nickel.. Le probleme c'est que je ne le fais pas en linux mais en Visual C++. Mais pour qu'il soit portative, j'utilise que des méthodes C/C++ compatibles. C'est pour cela, que j'avais regardé l'aide de Visual C++ mais je n'avais pas trouvé.

voici le code source pour que ca compile en Visual C++ (pour ceux qui ont le même probleme)

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
#include <stdlib.h> 
#include <stdio.h> 
 
/* 0 | 1 */ 
#define DBG 0 
 
#if DBG 
static void display_line (char const *s, int* p, int nb_col) 
{ 
   int j; 
 
   printf ("%s: ", s); 
   for (j = 0; j < nb_col; j++) 
   { 
      printf ("%-3d", p[j]); 
   } 
   printf ("\n"); 
} 
#endif 
 
/* Fonction de comparaison pour qsort() */ 
static int compare (void const *a, void const *b) 
{ 
   /* -ed- 
      Le tableau a trier a des elements de type int * 
      On recoit l'adresse de l'element de type int*, soit int ** 
   */ 
   int const **ppa = (int const **) a; 
   int const **ppb = (int const **)b; 
 
   /* -ed- on recupere l'adresse de la ligne  */ 
   int const *pa = *ppa; 
   int const *pb = *ppb; 
 
#if DBG 
 
   display_line("pa", pa, 2); 
   display_line("pb", pb, 2); 
#endif 
 
   /* -ed- on teste la colonne 1 */ 
   return pa[1] - pb[1]; 
} 
 
/* -ed- creation dynamique du tableau */ 
static int** create(int nb_lin, int nb_col) 
{ 
   int **pp = (int **)malloc (sizeof * pp * nb_lin); 
 
   if (pp != NULL) 
   { 
      int i; 
      for (i = 0; i < nb_lin; i++) 
      { 
         pp[i] =(int *) malloc (sizeof * pp[i] * nb_col); 
      } 
   } 
   return pp; 
} 
 
/* -ed- creation dynamique du tableau */ 
void delete2(int**pp, int nb_lin) 
{ 
   if (pp != NULL) 
   { 
      int i; 
      for (i = 0; i < nb_lin; i++) 
      { 
         free (pp[i]), pp[i] = NULL; 
      } 
   } 
   free (pp), pp = NULL; 
} 
 
void display (int** pp, int nb_lin, int nb_col) 
{ 
   int i; 
   for (i = 0; i < nb_lin; i++) 
   { 
      int j; 
      for (j = 0; j < nb_col; j++) 
      { 
         printf ("%3d", pp[i][j]); 
      } 
      printf ("\n"); 
   } 
} 
 
int main (void) 
{ 
   int nb_lin = 4; 
   int nb_col = 2; 
   int** tab2D = create (nb_lin, nb_col); 
 
   tab2D[0][0] = 10 ; 
   tab2D[0][1] = 15; 
 
   tab2D[1][0] = 2 ; 
   tab2D[1][1] = 6; 
 
   tab2D[2][0] = 9 ; 
   tab2D[2][1] = 18; 
 
   tab2D[3][0] = 5 ; 
   tab2D[3][1] = 5; 
 
   display (tab2D, nb_lin, nb_col); 
 
   // Appel de la fonction de tri 
   { 
      /* -ed- verifier que l'on passe les bons parametres */ 
      size_t nb_membres = nb_lin; 
      size_t sz_membre = sizeof * tab2D; 
      printf ("nb = %u sz = %u\n", (unsigned) nb_membres , (unsigned) sz_membre); 
 
      qsort (tab2D, nb_membres , sz_membre, compare); 
   } 
 
   display (tab2D, nb_lin, nb_col); 
 
   delete2(tab2D, nb_lin); 
 
   return 0; 
}

**Emmanuel Delahaye** · 26/01/2006, 20h22

Envoyé par sniperseb

Je te remercie, il marche nickel.. Le probleme c'est que je ne le fais pas en linux mais en Visual C++.

Le code que j'ai fourni est standard. Il et indépendant de la plateforme (pour info, il a été compilé et testé sur PC/XP/mingw)

Mais pour qu'il soit portative,

portable...

j'utilise que des méthodes C/C++ compatibles.

C/C++, ça n'existe pas. C et C++ sont des langages différents qu'il convient de ne pas mélanger.

C'est pour cela, que j'avais regardé l'aide de Visual C++ mais je n'avais pas trouvé.

voici le code source pour que ca compile en Visual C++ (pour ceux qui ont le même probleme)

: Je ne vois pas bien ce qu'il faut changer...

Code :

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

1
2
 
   int const **ppa = (int const **) a;

NON ! Tu as compilé en C++ !

Si tu fais du C, il faut apprendre à utiliser le compilateur C de Visual C++ :
Extension .c au lieu de .cpp, reglages...

Si tu fais du C++, tu te trompes de forum, et qsort() est obsolete. Il y a certainement mieux et plus facile à utiliser dans la STL (enfin, j'espère, sinon, c'était pas la peine d'avoir inventé cette usine à gaz...).

Qsort sur un tableau en 2D

C

Vue hybride

Discussions similaires

Partager

Partager