Problem using qsort(). Please help!

T

t_pantel

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
 
R

Ravi Uday

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);
}
Click to expand...

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
Click to expand...
 
D

dandelion

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);
}
Click to expand...

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!
Click to expand...

That is not explained by the code you presented, as far as i can see.
 
C

Chris Croughton

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);
}
Click to expand...

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?
Click to expand...

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
 
A

Al Bowers

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);
}
Click to expand...

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);
Click to expand...

What is match?

What am I doing wrong?
Click to expand...
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.val = 30-i;
test.code = i;
}

puts("\tUnsorted. First Five");
for(i = 0; i < 5; i++)
printf("test[%hd].val = %hd test[%hd].code = %hd\n",
i,test.val,i,test.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.val,i,test.code);
return 0;
}
 
C

CBFalconer

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);
}
Click to expand...

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 said:
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?
Click to expand...

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.
 
L

Lawrence Kirby

On Tue, 07 Dec 2004 16:15:59 +0530, Ravi Uday wrote:

....
how about :

if ( (GROUPED *)arg1->val > 0 )
return 1;
if ( (GROUPED *)arg1->val < 0 )
return -1;

return 0;
Click to expand...


The function is supposed to compare the elements pointed at by arg1 and
arg2. This doesn't even look at arg2.

Lawrence
 
L

Lawrence Kirby

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.
Click to expand...

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
 
T

t_pantel

dandelion said:
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);
}
Click to expand...

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!
Click to expand...

That is not explained by the code you presented, as far as i can see.
Click to expand...
 
R

Ravi Uday

Lawrence said:
On Tue, 07 Dec 2004 16:15:59 +0530, Ravi Uday wrote:

...





The function is supposed to compare the elements pointed at by arg1 and
arg2. This doesn't even look at arg2.
Click to expand...
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;
}
 
K

Keith Thompson

Ravi Uday said:
Lawrence Kirby wrote: [...]
The function is supposed to compare the elements pointed at by arg1
and
arg2. This doesn't even look at arg2.
Click to expand...
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;
}
Click to expand...

This still doesn't look at arg2, but it's just an easily correctable
typo.
 
R

Ravi Uday

Keith said:
Ravi Uday said:
Lawrence Kirby wrote:
[...]
The function is supposed to compare the elements pointed at by arg1
and
arg2. This doesn't even look at arg2.
Click to expand...

Oops ! apologies.
It should have been

int compare( const void *arg1, const void *arg2 )
{
GROUPED *left = (GROUPED *)arg1;
GROUPED *right = (GROUPED *)arg1;
Click to expand...
Click to expand...
^^^^
Yes, it should have been 'arg2'
sorry!
 
L

Lawrence Kirby

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;
Click to expand...

Make that arg2.
if (left->val > right->val)
return 1;
if (left->val < right->val)
return -1;

return 0;
}
Click to expand...

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
 
C

CBFalconer

Ravi said:
Keith said:
Ravi Uday said:
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;
Click to expand...
Click to expand...
^^^^
Yes, it should have been 'arg2'
Click to expand...

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);
 
R

Ravi Uday

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);
Click to expand...

You mean
return (*left->val > *right->val ) - (*left->val < *right->val);
 
C

CBFalconer

Ravi said:
You mean
return (*left->val > *right->val ) - (*left->val < *right->val);
Click to expand...

Thanks for the correction. Please maintain attributions for
material you quote.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Qsort() messing with my entire Code 0
Qsort() is messing with my entire Code!!! 0
Code help please 4
Adding adressing of IPv6 to program 1
Please help with C programming to save GPS reception data in Raspberry Pi. 0
qsort man page 23
qsort returning index 2
qsort problem 12

Members online

No members online now.
Total: 36 (members: 1, guests: 35)
Robots: 224

Forum statistics

Threads
473,755
Messages
2,569,537
Members
45,022
Latest member
MaybelleMa

Latest Threads

Top