t_pantel@yahoo.com
Guest
Posts: n/a

 12-07-2004
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
Guest
Posts: n/a

 12-07-2004

http://www.velocityreviews.com/forums/(E-Mail Removed) 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);
> }

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

dandelion
Guest
Posts: n/a

 12-07-2004

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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.

Chris Croughton
Guest
Posts: n/a

 12-07-2004
On 7 Dec 2004 02:14:37 -0800, (E-Mail Removed)
<(E-Mail Removed)> 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.

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

Al Bowers
Guest
Posts: n/a

 12-07-2004

(E-Mail Removed) 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)?-1g1->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: (E-Mail Removed) (remove the x to send email)
http://www.geocities.com/abowers822/

CBFalconer
Guest
Posts: n/a

 12-07-2004
(E-Mail Removed) 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);
> }

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 ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.

Lawrence Kirby
Guest
Posts: n/a

 12-08-2004
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);
>> }

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

Lawrence Kirby
Guest
Posts: n/a

 12-08-2004
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

t_pantel@yahoo.com
Guest
Posts: n/a

 12-08-2004

dandelion wrote:
> <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) 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.

Ravi Uday
Guest
Posts: n/a

 12-08-2004

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

>>
>>
>> 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;
}