qsort

[John Smith]

I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help?

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, 7, 4, &compare);
for(idx=0; idx<7; ++idx)
printf("%d\t", array[idx]);
printf("\n");

return 0;
}

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}

[Eric Sosman]

Re: qsort

John Smith wrote:[color=blue]
> I'm trying to figure out qsort(). I haven't seen any practical examples,
> only synopsis. In the code below, the array is not sorted. Can someone
> give me some help?
>
> #include <stdio.h>
> #include <stdlib.h>
> int compare(const void* a, const void* b);
>
> int main(void)
> {
> int idx;
> int array[] = {243, 12, 99, 106, 122, 77, 242};
>
> qsort(array, 7, 4, &compare);[/color]

The `&' is harmless, but unnecessary. The `4' may
be true for your C implementation, but is not universal:
each C implementation chooses its own "best" size for
`int', and different implementations choose differently.
For portability, write `sizeof array[0]' instead.
[color=blue]
> for(idx=0; idx<7; ++idx)
> printf("%d\t", array[idx]);
> printf("\n");
>
> return 0;
> }
>
> int compare(const void* a, const void* b)
> {
> if(a < b) return -1;
> if(a == b) return 0;
> if(a > b) return 1;
> }[/color]

Here's your difficulty. The comparison function's
arguments are not two array elements, but pointers to
two array elements. You are comparing the pointers, but
you want to compare the pointed-to objects. Here is one
way to do it:

int compare(const void *a, const void *b) {
int u = *(const int*)a;
int v = *(const int*)b;
if (u < v) ...

--
Eric.Sosman@sun .com

[Trent Buck]

Re: qsort

Quoth John Smith on or about 2004-11-17:[color=blue]
> if(a < b) return -1;
> if(a == b) return 0;
> if(a > b) return 1;[/color]

First of all, shouldn't these be dereferenced?

[Andrey Tarasevich]

Re: qsort

John Smith wrote:[color=blue]
> I'm trying to figure out qsort(). I haven't seen any practical examples,
> only synopsis. In the code below, the array is not sorted. Can someone
> give me some help?
>
> #include <stdio.h>
> #include <stdlib.h>
> int compare(const void* a, const void* b);
>
> int main(void)
> {
> int idx;
> int array[] = {243, 12, 99, 106, 122, 77, 242};
>
> qsort(array, 7, 4, &compare);
> for(idx=0; idx<7; ++idx)
> printf("%d\t", array[idx]);
> printf("\n");
>
> return 0;
> }
>
> int compare(const void* a, const void* b)
> {
> if(a < b) return -1;
> if(a == b) return 0;
> if(a > b) return 1;
> }[/color]

Inside your 'compare' implementation you are comparing pointers instead
of comparing the values pointed by those pointers. You are supposed to
do the latter, not the former. For example, you can do it as follows

int compare(const void* a, const void* b)
{
int ia = *(const int*) a;
int ib = *(const int*) b;
return (ia > ib) - (ia < ib);
}

Also, it makes more sense to form arguments of 'qsort' by using
'sizeof', instead of specifying concrete values explicitly

qsort(array, sizeof array / sizeof *array, sizeof *array, &compare);

--
Best regards,
Andrey Tarasevich

[pete]

Re: qsort

John Smith wrote:[color=blue]
>
> I'm trying to figure out qsort(). I haven't seen any practical examples,
> only synopsis. In the code below, the array is not sorted. Can someone
> give me some help?
>
> #include <stdio.h>
> #include <stdlib.h>
> int compare(const void* a, const void* b);
>
> int main(void)
> {
> int idx;
> int array[] = {243, 12, 99, 106, 122, 77, 242};
>
> qsort(array, 7, 4, &compare);
> for(idx=0; idx<7; ++idx)
> printf("%d\t", array[idx]);
> printf("\n");
>
> return 0;
> }
>
> int compare(const void* a, const void* b)
> {
> if(a < b) return -1;
> if(a == b) return 0;
> if(a > b) return 1;
> }[/color]

#include <stdio.h>
#include <stdlib.h>

#define NELM (sizeof array / sizeof *array)

int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, NELM, sizeof *array, compare);
for (idx = 0; idx < NELM; ++idx) {
printf("%d\t", array[idx]);
}
putchar('\n');
return 0;
}

int compare(const void* a, const void* b)
{
const int aa = *(int*)a;
const int bb = *(int*)b;

return bb > aa ? -1 : aa > bb;
}

--
pete

[Robert Harris]

Re: qsort

pete wrote:
[color=blue]
> [snip][/color]
[color=blue]
> int compare(const void* a, const void* b)
> {
> const int aa = *(int*)a;[/color]
should be:
const int aa = *(const int *)a;[color=blue]
> const int bb = *(int*)b;
>
> return bb > aa ? -1 : aa > bb;[/color]
return aa - bb;

would be the usual idiom.[color=blue]
> }
>[/color]

[pete]

Re: qsort

Robert Harris wrote:[color=blue]
>
> pete wrote:
>[color=green]
> > [snip][/color]
>[color=green]
> > int compare(const void* a, const void* b)
> > {
> > const int aa = *(int*)a;[/color]
> should be:
> const int aa = *(const int *)a;[/color]

It makes no difference.
You wind up with const int aa, either way.
[color=blue][color=green]
> > const int bb = *(int*)b;
> >
> > return bb > aa ? -1 : aa > bb;[/color]
> return aa - bb;
>
> would be the usual idiom.[/color]

(aa - bb) is entirely unacceptable
as a generic compar function expression.
If aa equals INT_MAX and bb equals -1,
then you have undefined behavior.
[color=blue][color=green]
> > }[/color][/color]

--
pete

[Charlie Gordon]

Re: qsort

"John Smith" <JSmith@mail.ne t> wrote in message
news:5qNmd.2524 45$%k.66766@pd7 tw2no...[color=blue]
> I'm trying to figure out qsort(). I haven't seen any practical examples,
> only synopsis. In the code below, the array is not sorted. Can someone
> give me some help?[/color]
[color=blue]
> int compare(const void* a, const void* b)
> {
> if(a < b) return -1;
> if(a == b) return 0;
> if(a > b) return 1;
> }[/color]

The compare function is incorrect.
Other replies have given correct alternatives.
Here is my question :

What is the semantics of comparing void* for anything but equality ?
It is non standard to subtract void pointers (but a dubious gcc extension)
What about comparison ? Is it also an extension or is it defined in the
standard ?

Chqrlie.

[Eric Sosman]

Re: qsort

Charlie Gordon wrote:[color=blue]
> "John Smith" <JSmith@mail.ne t> wrote in message
> news:5qNmd.2524 45$%k.66766@pd7 tw2no...[color=green]
>>
>>int compare(const void* a, const void* b)
>>{
>> if(a < b) return -1;
>> if(a == b) return 0;
>> if(a > b) return 1;
>>}[/color]
>
> The compare function is incorrect.
> Other replies have given correct alternatives.
> Here is my question :
>
> What is the semantics of comparing void* for anything but equality ?
> It is non standard to subtract void pointers (but a dubious gcc extension)
> What about comparison ? Is it also an extension or is it defined in the
> standard ?[/color]

The comparison is well-defined (as I learned to my
surprise not long ago) under the usual condition that
the two pointers point to or just after the same array.
qsort() guarantees this (although bsearch() obviously
does not), so the comparison is valid.

However, the fact that the comparison is valid doesn't
imply that it's usable by qsort()! The compare() function
must define a consistent ordering, even while qsort() is
busy rearranging the array. If the compare() function's
result changes as the items are shuffled about, the ordering
is inconsistent and qsort()'s behavior is undefined.

Various people have run afoul of this by trying to
compare the pointers to equal elements in an attempt to
achieve a stable sort, e.g.

int compare(const void *p, const void *q) {
int a = *(const int*)p;
int b = *(const int*)q;

if (a < b) return -1;
if (a > b) return +1;

/* Equal elements; try for stability */
if (p < q) return -1;
if (p > q) return +1;
return 0; /* stupid qsort()! */
}

is wrong, R-O-N-G, wrong. The outcome of comparing two
equal integers would depend on their relative locations
in the array, and these locations can change as qsort()
does its work.

--
Eric.Sosman@sun .com

[Andrey Tarasevich]

Re: qsort

Robert Harris wrote:[color=blue]
> ...[color=green]
>> int compare(const void* a, const void* b)
>> {
>> const int aa = *(int*)a;[/color]
> should be:
> const int aa = *(const int *)a;[color=green]
>> const int bb = *(int*)b;
>>
>> return bb > aa ? -1 : aa > bb;[/color]
> return aa - bb;
>
> would be the usual idiom.[/color]

The usual idiom would be

return (aa > bb) - (aa < bb);

A mere 'aa - bb' can produce signed overflow, which makes it entirely
useless.

--
Best regards,
Andrey Tarasevich

[Lawrence Kirby]

Re: qsort

On Thu, 18 Nov 2004 12:18:56 +0000, pete wrote:
[color=blue]
> Robert Harris wrote:[color=green]
>>
>> pete wrote:
>>[color=darkred]
>> > [snip][/color]
>>[color=darkred]
>> > int compare(const void* a, const void* b)
>> > {
>> > const int aa = *(int*)a;[/color]
>> should be:
>> const int aa = *(const int *)a;[/color]
>
> It makes no difference.
> You wind up with const int aa, either way.[/color]

True the int* cast is correct, but not casting away const
is better style. Reasonable compiler often will
issue a warning about that or can be made to, and it is
a good warning to turn on.

Lawrence

[Lawrence Kirby]

Re: qsort

On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote:

....
[color=blue]
> The comparison is well-defined (as I learned to my
> surprise not long ago) under the usual condition that
> the two pointers point to or just after the same array.
> qsort() guarantees this[/color]

I don't see anything in the description of qsort() that guarantees this.
It would be quite reasonable for an implementation for qsort() to copy an
element of the array into a local temporary and compare against that. This
is a natural thing to do in some sorting algorithms.

Lawrence

[Eric Sosman]

Re: qsort

Lawrence Kirby wrote:[color=blue]
> On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote:
>
> ...
>
>[color=green]
>> The comparison is well-defined (as I learned to my
>>surprise not long ago) under the usual condition that
>>the two pointers point to or just after the same array.
>>qsort() guarantees this[/color]
>
>
> I don't see anything in the description of qsort() that guarantees this.[/color]

The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]

--
Eric.Sosman@sun .com

[Lawrence Kirby]

Re: qsort

On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
[color=blue]
> Lawrence Kirby wrote:[/color]

....
[color=blue][color=green]
>> I don't see anything in the description of qsort() that guarantees this.[/color]
>
> The C89 wording isn't clear, but C99 makes it explicit:
>
> 7.20.5 Searching and sorting utilities
> /2/ The implementation shall ensure that [...] both
> arguments (when called from qsort), are pointers to
> elements of the array. [...][/color]

OK, it is required in C99. Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.

Lawrence

[pete]

Re: qsort

Lawrence Kirby wrote:[color=blue]
>
> On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
>[color=green]
> > Lawrence Kirby wrote:[/color]
>
> ...
>[color=green][color=darkred]
> >> I don't see anything in the description of qsort()
> >> that guarantees this.[/color]
> >
> > The C89 wording isn't clear, but C99 makes it explicit:
> >
> > 7.20.5 Searching and sorting utilities
> > /2/ The implementation shall ensure that [...] both
> > arguments (when called from qsort), are pointers to
> > elements of the array. [...][/color]
>
> OK, it is required in C99.
> Very strange though, it potentially reduces the
> efficiency of the implementation for no obvious benefit.[/color]

I must be misunderstandin g what you're saying.
I don't see how you can write a compar function without knowing
that the arguments are pointers to array elements.

Is this the same thing as what you're talking about?
My C89 last draft has:

4.10.5.2 The qsort function
The contents of the array are sorted in ascending order according
to a comparison function pointed to by compar , which is called with
two arguments that point to the objects being compared.

--
pete