449,110 Members | 990 Online
Need help? Post your question and get tips & solutions from a community of 449,110 IT Pros & Developers. It's quick & easy.

 P: n/a I 've got the following structure: typedef struct GROUPED { short val ; short code; short group; short forecast_cd; short double_ind; short min; short max; } GROUPED; and an define array: GROUPED test[30]; A possible example for the values tha this structure array could contain are: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=111 test[1].code=112 test[2].code=113 test[2].code=114 Suppose that the remainung fields are 0. I want to sort the results by "val" and I am trying to use qsort() to achieve this. My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); The result after calling qsort is this: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=112 test[1].code=111 test[2].code=113 test[2].code=114 As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! What am I doing wrong? Thanks a lot. Thanos Nov 14 '05 #1
16 Replies

 P: n/a t_******@yahoo.com wrote: I 've got the following structure: typedef struct GROUPED { short val ; short code; short group; short forecast_cd; short double_ind; short min; short max; } GROUPED; and an define array: GROUPED test[30]; A possible example for the values tha this structure array could contain are: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=111 test[1].code=112 test[2].code=113 test[2].code=114 Suppose that the remainung fields are 0. I want to sort the results by "val" and I am trying to use qsort() to achieve this. My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } how about : if ( (GROUPED *)arg1->val > 0 ) return 1; if ( (GROUPED *)arg1->val < 0 ) return -1; return 0; and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); The result after calling qsort is this: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=112 test[1].code=111 test[2].code=113 test[2].code=114 As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! What am I doing wrong? Thanks a lot. Thanos Nov 14 '05 #2

 P: n/a wrote in message news:7b*************************@posting.google.co m... int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } By the looks of it, your compare function does not lead me to expect the output sequence you posted. There are several things wrong with it. I'll just omit the type-cast for clarity for a moment. 1. If arg1->val == arg2->val == 0, your comparison produces -1, which is wrong. It should have been 0 since arg1->val == arg2->val. 2. If arg1->val == arg2->val == 1, your comparison produces -1, which is wrong, too. The comparison value should return * -1 if and only if arg1->val < arg2->val * 0 if and only if arg1->val == arg2->val * 1 if and only if arg1->val > arg2->val So int compare( const void *arg1, const void *arg2 ) { if(arg1->val > arg2->val) { return 1; } else if (arg1->val < arg2->val) { return -1; } else { return 0; } } and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); The result after calling qsort is this: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=112 test[1].code=111 test[2].code=113 test[2].code=114 As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! That is not explained by the code you presented, as far as i can see. Nov 14 '05 #3

 P: n/a t_******@yahoo.com wrote: I 've got the following structure: typedef struct GROUPED { short val ; short code; short group; short forecast_cd; short double_ind; short min; short max; } GROUPED; and an define array: GROUPED test[30]; A possible example for the values tha this structure array could contain are: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=111 test[1].code=112 test[2].code=113 test[2].code=114 Suppose that the remainung fields are 0. I want to sort the results by "val" and I am trying to use qsort() to achieve this. My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } The compare function is flawed in that you are comparing against zero instead of comparing against each other. It should be something like: int compare2(const void *v1, const void *v2) { const GROUPED *g1 = v1; const GROUPED *g2 = v2; if(g1->val < g2->val) return -1; if(g1->val > g2->val) return 1; return 0; } and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); What is match? What am I doing wrong? Redo the compare funcition and try again. Example: #include #include typedef struct GROUPED { short val ; short code; short group; short forecast_cd; short double_ind; short min; short max; } GROUPED; int compare(const void *v1, const void *v2) { const GROUPED *g1 = v1; const GROUPED *g2 = v2; return (g1->valval)?-1:(g1->val!=g2->val); } int main(void) { GROUPED test[30] = {{0}}; short i; for(i = 0; i < 30;i++) { /* Assign values to val and code */ test[i].val = 30-i; test[i].code = i; } puts("\tUnsorted. First Five"); for(i = 0; i < 5; i++) printf("test[%hd].val = %hd test[%hd].code = %hd\n", i,test[i].val,i,test[i].code); qsort(test,30,sizeof *test,compare2); puts("\n\tSorted(Ascending) by val. First Five"); for(i = 0; i < 5; i++) printf("test[%hd].val = %hd test[%hd].code = %hd\n", i,test[i].val,i,test[i].code); return 0; } -- Al Bowers Tampa, Fl USA mailto: xa******@myrapidsys.com (remove the x to send email) http://www.geocities.com/abowers822/ Nov 14 '05 #4

 P: n/a t_******@yahoo.com wrote: I 've got the following structure: typedef struct GROUPED { short val ; short code; short group; short forecast_cd; short double_ind; short min; short max; } GROUPED; and an define array: GROUPED test[30]; A possible example for the values tha this structure array could contain are: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=111 test[1].code=112 test[2].code=113 test[2].code=114 Suppose that the remainung fields are 0. I want to sort the results by "val" and I am trying to use qsort() to achieve this. My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } Your comparison is faulty. Try: int compare(const void *arg1, const void *arg2) { GROUPED *left = arg1; GROUPED *right = arg2; return (left->val > right->val) - (left->val < right->val); } and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); The result after calling qsort is this: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=112 test[1].code=111 test[2].code=113 test[2].code=114 As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! What am I doing wrong? In this regard, nothing. Quicksort (and thus qsort, which may be quicksort) is not guaranteed to perform a stable sort. For a stable sort I recommend mergesort. This part is an algorithmic question, and is actually off-topic in c.l.c. You can get a similar effect by including the code field in the comparison whenever the val based result is zero. This will simply sort on the basis of both fields, and is still not stable. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #5

 P: n/a On 7 Dec 2004 02:14:37 -0800, t_******@yahoo.com wrote: I want to sort the results by "val" and I am trying to use qsort() to achieve this. My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } I'm not sure what you are trying to achieve here. You never return saying that the arguments compare equal, and do you really mean that 0 is greater than 1 and -1 is greater than 0? your first two tests will give that result. How about: if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); if (((GROUPED *)arg1)->val < ((GROUPED*)arg2)->val) return (-1); return 0; (and forget the first two tests). As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! What am I doing wrong? Well, according to your compare function it never returns anything saying that the values are equal, so how is qsort supposed to know? However, even if you correct that you still won't guarantee the same order as originally in the array for values which compare equal. The spec. says: 7.20.5.2 The qsort function 4 If two elements compare as equal, their order in the resulting sorted array is unspecified. Specifically, the "Quicksort" algorithm cannot guarantee that elements comparing equal will be returned in any consistent order at all. If you want to guarantee that values comparing equal will keep their order you need a different algorithm, like C++'s "stable_sort". This is outside the standard C library, though, you may be best looking for an existing implementation or reading up about it in Knuth or another book on algorithms. Or you can fudge it, for instance the GNU libc manual suggests: If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary. It's also non-portable, of course. You could also add an element to your structure which only consists of the element number, set it sequentially and compare those if the values compare equal (note that since you know those values will never be equal the test can be simplified). See http://en.wikipedia.org/wiki/Sort_algorithm for a list of types of sort algorithms, including their speed (order) and other limitations (like extra memory). In general, stable sort algorithms are slower than unstable ones although all of them depend on the data (some actually taking longer if the data are already sorted!). Chris C Nov 14 '05 #6

 P: n/a On Tue, 07 Dec 2004 16:15:59 +0530, Ravi Uday wrote: .... My comparison function is: int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } how about : if ( (GROUPED *)arg1->val > 0 ) return 1; if ( (GROUPED *)arg1->val < 0 ) return -1; return 0; The function is supposed to compare the elements pointed at by arg1 and arg2. This doesn't even look at arg2. Lawrence Nov 14 '05 #7

 P: n/a On Tue, 07 Dec 2004 12:30:05 +0000, Chris Croughton wrote: .... If you want to guarantee that values comparing equal will keep their order you need a different algorithm, like C++'s "stable_sort". This is outside the standard C library, though, you may be best looking for an existing implementation or reading up about it in Knuth or another book on algorithms. Or you can fudge it, for instance the GNU libc manual suggests: If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary. It's also non-portable, of course. More than that it is completely wrong. You cannot use addresses to ensure stability. This will guarantee that the comparison function is invalid. The positions of particular data elements changes during the sort, and for typical algorithms better than O(N^^2) an element can be moved significant distances in the array, possibly jumping over other elements with equal data. As well as not creating stability a comparison function using address data would give inconsistent results, resulting in undefined behaviour for the overall sort. Lawrence Nov 14 '05 #8

 P: n/a dandelion wrote: wrote in message news:7b*************************@posting.google.co m... int compare( const void *arg1, const void *arg2 ) { if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1); } By the looks of it, your compare function does not lead me to expect the output sequence you posted. There are several things wrong with it. I'll just omit the type-cast for clarity for a moment. 1. If arg1->val == arg2->val == 0, your comparison produces -1, which is wrong. It should have been 0 since arg1->val == arg2->val. 2. If arg1->val == arg2->val == 1, your comparison produces -1, which is wrong, too. The comparison value should return * -1 if and only if arg1->val < arg2->val * 0 if and only if arg1->val == arg2->val * 1 if and only if arg1->val > arg2->val So int compare( const void *arg1, const void *arg2 ) { if(arg1->val > arg2->val) { return 1; } else if (arg1->val < arg2->val) { return -1; } else { return 0; } } and I call qsort like this: qsort(match, (size_t)30, sizeof(GROUPED), compare); The result after calling qsort is this: test[0].val=1 test[1].val=1 test[2].val=2 test[3].val=3 test[0].code=112 test[1].code=111 test[2].code=113 test[2].code=114 As it is obvious it reverses test[0].code and test[1].code values that is, the values of the .code that have the same .val value! That is not explained by the code you presented, as far as i can see. Nov 14 '05 #9

 P: n/a Lawrence Kirby wrote: On Tue, 07 Dec 2004 16:15:59 +0530, Ravi Uday wrote: ...My comparison function is:int compare( const void *arg1, const void *arg2 ){ if (((GROUPED *)arg1)->val==0) return 1; if (((GROUPED *)arg2)->val==0) return -1; if (((GROUPED *)arg1)->val > ((GROUPED*)arg2)->val) return (1); return (-1);}how about : if ( (GROUPED *)arg1->val > 0 ) return 1; if ( (GROUPED *)arg1->val < 0 ) return -1; return 0; The function is supposed to compare the elements pointed at by arg1 and arg2. This doesn't even look at arg2. Oops ! apologies. It should have been int compare( const void *arg1, const void *arg2 ) { GROUPED *left = (GROUPED *)arg1; GROUPED *right = (GROUPED *)arg1; if (left->val > right->val) return 1; if (left->val < right->val) return -1; return 0; } Nov 14 '05 #10

 P: n/a wrote in message news:11**********************@z14g2000cwz.googlegr oups.com... Yessss..... ? Nov 14 '05 #11

 P: n/a Ravi Uday writes: Lawrence Kirby wrote: [...] The function is supposed to compare the elements pointed at by arg1 and arg2. This doesn't even look at arg2. Oops ! apologies. It should have been int compare( const void *arg1, const void *arg2 ) { GROUPED *left = (GROUPED *)arg1; GROUPED *right = (GROUPED *)arg1; if (left->val > right->val) return 1; if (left->val < right->val) return -1; return 0; } This still doesn't look at arg2, but it's just an easily correctable typo. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 14 '05 #12

 P: n/a Keith Thompson wrote: Ravi Uday writes:Lawrence Kirby wrote: [...]The function is supposed to compare the elements pointed at by arg1andarg2. This doesn't even look at arg2.Oops ! apologies.It should have beenint compare( const void *arg1, const void *arg2 ){GROUPED *left = (GROUPED *)arg1;GROUPED *right = (GROUPED *)arg1; ^^^^ Yes, it should have been 'arg2' sorry! if (left->val > right->val) return 1; if (left->val < right->val) return -1; return 0;} This still doesn't look at arg2, but it's just an easily correctable typo. Nov 14 '05 #13

 P: n/a On Wed, 08 Dec 2004 17:38:47 +0530, Ravi Uday wrote: .... Oops ! apologies. It should have been int compare( const void *arg1, const void *arg2 ) { GROUPED *left = (GROUPED *)arg1; GROUPED *right = (GROUPED *)arg1; Make that arg2. if (left->val > right->val) return 1; if (left->val < right->val) return -1; return 0; } That looks good but don't cast away const when you don't need to, and you very rarely need to. int compare( const void *arg1, const void *arg2 ) { const GROUPED *left = arg1; const GROUPED *right = arg2; if (left->val > right->val) return 1; if (left->val < right->val) return -1; return 0; } You don't then even need the cast. Lawrence Nov 14 '05 #14

 P: n/a Ravi Uday wrote: Keith Thompson wrote: Ravi Uday writes: Lawrence Kirby wrote: [...] The function is supposed to compare the elements pointed at by arg1 and arg2. This doesn't even look at arg2. Oops ! apologies. It should have been int compare( const void *arg1, const void *arg2 ) { GROUPED *left = (GROUPED *)arg1; GROUPED *right = (GROUPED *)arg1; ^^^^ Yes, it should have been 'arg2' However it should not have any cast. And the local variables should have the 'const' attribute. const GROUPED *left = arg1, *right = arg2; and you can avoid instruction stream flushing with: return (*left > *right) - (*left < *right); -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #15

 P: n/a int compare( const void *arg1, const void *arg2 ){GROUPED *left = (GROUPED *)arg1;GROUPED *right = (GROUPED *)arg1; ^^^^Yes, it should have been 'arg2' However it should not have any cast. And the local variables should have the 'const' attribute. const GROUPED *left = arg1, *right = arg2; and you can avoid instruction stream flushing with: return (*left > *right) - (*left < *right); You mean return (*left->val > *right->val ) - (*left->val < *right->val); Nov 14 '05 #16

 P: n/a Ravi Uday wrote: > int compare( const void *arg1, const void *arg2 )> {> GROUPED *left = (GROUPED *)arg1;> GROUPED *right = (GROUPED *)arg1; Yes, it should have been 'arg2' However it should not have any cast. And the local variables should have the 'const' attribute. const GROUPED *left = arg1, *right = arg2; and you can avoid instruction stream flushing with: return (*left > *right) - (*left < *right); You mean return (*left->val > *right->val ) - (*left->val < *right->val); Thanks for the correction. Please maintain attributions for material you quote. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #17

### This discussion thread is closed

Replies have been disabled for this discussion.