Problem using qsort(). Please help!

[t_pantel@yahoo.com]

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

[Ravi Uday]

Re: Problem using qsort(). Please help!



t_pantel@yahoo. com wrote:[color=blue]
> 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);
> }[/color]

how about :

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

return 0;

[color=blue]
>
> 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[/color]

[dandelion]

Re: Problem using qsort(). Please help!


<t_pantel@yahoo .com> wrote in message
news:7b80c3dc.0 412070214.8b6a4 6b@posting.goog le.com...
<snip>
[color=blue]
> 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);
> }[/color]

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;
}
}
[color=blue]
>
> 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![/color]

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

[Al Bowers]

Re: Problem using qsort(). Please help!



t_pantel@yahoo. com wrote:[color=blue]
> 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);
> }[/color]

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;
}
[color=blue]
> and I call qsort like this:
>
> qsort(match, (size_t)30, sizeof(GROUPED) , compare);[/color]

What is match?

[color=blue]
> What am I doing wrong?[/color]
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("\tUnsorte d. 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,s izeof *test,compare2) ;
puts("\n\tSorte d(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: xabowers@myrapi dsys.com (remove the x to send email)

http://www.geocities.com/abowers822/

[CBFalconer]

Re: Problem using qsort(). Please help!

t_pantel@yahoo. com wrote:[color=blue]
>
> 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);
> }[/color]

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);
}[color=blue]
>
> 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?[/color]

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 (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Chris Croughton]

Re: Problem using qsort(). Please help!

On 7 Dec 2004 02:14:37 -0800, t_pantel@yahoo. com
<t_pantel@yahoo .com> wrote:
[color=blue]
> 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);
> }[/color]

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).
[color=blue]
> 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?[/color]

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_sor t". 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

[Lawrence Kirby]

Re: Problem using qsort(). Please help!

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

....
[color=blue][color=green]
>> 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);
>> }[/color]
>
> how about :
>
> if ( (GROUPED *)arg1->val > 0 )
> return 1;
> if ( (GROUPED *)arg1->val < 0 )
> return -1;
>
> return 0;[/color]


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

Lawrence

[Lawrence Kirby]

Re: Problem using qsort(). Please help!

On Tue, 07 Dec 2004 12:30:05 +0000, Chris Croughton wrote:

....
[color=blue]
> If you want to guarantee that values comparing equal will keep their
> order you need a different algorithm, like C++'s "stable_sor t". 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.[/color]

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_pantel@yahoo.com]

Re: Problem using qsort(). Please help!


dandelion wrote:[color=blue]
> <t_pantel@yahoo .com> wrote in message
> news:7b80c3dc.0 412070214.8b6a4 6b@posting.goog le.com...
> <snip>
>[color=green]
> > 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);
> > }[/color]
>
> By the looks of it, your compare function does not lead me to expect[/color]
the[color=blue]
> output sequence you posted. There are several things wrong with it.[/color]
I'll[color=blue]
> just omit the type-cast for clarity for a moment.
>
> 1. If arg1->val == arg2->val == 0, your comparison produces -1, which[/color]
is[color=blue]
> wrong. It should have been 0 since arg1->val == arg2->val.
>
> 2. If arg1->val == arg2->val == 1, your comparison produces -1,[/color]
which is[color=blue]
> 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;
> }
> }
>[color=green]
> >
> > 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[/color][/color]
that[color=blue][color=green]
> > is, the values of the .code that have the same .val value![/color]
>
> That is not explained by the code you presented, as far as i can see.[/color]

[Ravi Uday]

Re: Problem using qsort(). Please help!



Lawrence Kirby wrote:[color=blue]
> On Tue, 07 Dec 2004 16:15:59 +0530, Ravi Uday wrote:
>
> ...
>
>[color=green][color=darkred]
>>>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);
>>>}[/color]
>>
>>how about :
>>
>> if ( (GROUPED *)arg1->val > 0 )
>> return 1;
>> if ( (GROUPED *)arg1->val < 0 )
>> return -1;
>>
>> return 0;[/color]
>
>
>
> The function is supposed to compare the elements pointed at by arg1 and
> arg2. This doesn't even look at arg2.
>[/color]
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;
}

[dandelion]

Re: Problem using qsort(). Please help!


<t_pantel@yahoo .com> wrote in message
news:1102507047 .888983.222320@ z14g2000cwz.goo glegroups.com.. .

<snip quote only post>

Yessss..... ?

[Keith Thompson]

Re: Problem using qsort(). Please help!

Ravi Uday <raviuday@gmail .com> writes:[color=blue]
> Lawrence Kirby wrote:[/color]
[...][color=blue][color=green]
>> The function is supposed to compare the elements pointed at by arg1
>> and
>> arg2. This doesn't even look at arg2.
>>[/color]
> 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;
> }[/color]

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

--
Keith Thompson (The_Other_Keit h) kst-u@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.

[Ravi Uday]

Re: Problem using qsort(). Please help!



Keith Thompson wrote:[color=blue]
> Ravi Uday <raviuday@gmail .com> writes:
>[color=green]
>>Lawrence Kirby wrote:[/color]
>
> [...]
>[color=green][color=darkred]
>>>The function is supposed to compare the elements pointed at by arg1
>>>and
>>>arg2. This doesn't even look at arg2.
>>>[/color]
>>
>>Oops ! apologies.
>>It should have been
>>
>>int compare( const void *arg1, const void *arg2 )
>>{
>>GROUPED *left = (GROUPED *)arg1;
>>GROUPED *right = (GROUPED *)arg1;[/color][/color]
^^^^
Yes, it should have been 'arg2'
sorry![color=blue][color=green]
>>
>> if (left->val > right->val)
>> return 1;
>> if (left->val < right->val)
>> return -1;
>>
>> return 0;
>>}[/color]
>
>
> This still doesn't look at arg2, but it's just an easily correctable
> typo.
>[/color]

[Lawrence Kirby]

Re: Problem using qsort(). Please help!

On Wed, 08 Dec 2004 17:38:47 +0530, Ravi Uday wrote:

....

[color=blue]
> Oops ! apologies.
> It should have been
>
> int compare( const void *arg1, const void *arg2 )
> {
> GROUPED *left = (GROUPED *)arg1;
> GROUPED *right = (GROUPED *)arg1;[/color]

Make that arg2.
[color=blue]
>
> if (left->val > right->val)
> return 1;
> if (left->val < right->val)
> return -1;
>
> return 0;
> }[/color]

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

[CBFalconer]

Re: Problem using qsort(). Please help!

Ravi Uday wrote:[color=blue]
> Keith Thompson wrote:[color=green]
>> Ravi Uday <raviuday@gmail .com> writes:[color=darkred]
>>> Lawrence Kirby wrote:[/color]
>>
>> [...]
>>[color=darkred]
>>>> 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;[/color][/color]
> ^^^^
> Yes, it should have been 'arg2'[/color]

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 (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!