By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,110 Members | 990 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,110 IT Pros & Developers. It's quick & easy.

Problem using qsort(). Please help!

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
Share this Question
Share on Google+
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

<t_******@yahoo.com> wrote in message
news:7b*************************@posting.google.co m...
<snip>
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 <stdio.h>
#include <stdlib.h>

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->val<g2->val)?-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.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #5

P: n/a
On 7 Dec 2004 02:14:37 -0800, t_******@yahoo.com
<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:
<t_******@yahoo.com> wrote in message
news:7b*************************@posting.google.co m...
<snip>
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

<t_******@yahoo.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...

<snip quote only post>

Yessss..... ?
Nov 14 '05 #11

P: n/a
Ravi Uday <ra******@gmail.com> 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 <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #12

P: n/a


Keith Thompson wrote:
Ravi Uday <ra******@gmail.com> 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'
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 <ra******@gmail.com> 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.
<http://cbfalconer.home.att.net> USE worldnet address!

Nov 14 '05 #15

P: n/a
<snip>
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:

<snip>
> 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.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #17

This discussion thread is closed

Replies have been disabled for this discussion.