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

noop comparator for qsort

P: n/a
The fourth argument is a comparator that returns `an integer less than,
equal to, or greater than zero' depending on the ordering of its
arguments.

If I don't care about the order and simply want qsort() to run as
quickly as possible, how should the comparator be defined?

If qsort were stable, the following would be best:

int
compare (void *x, void *y)
{
return 0;
}

....is this still true for a possibly non-stable qsort()?

-trent
Nov 14 '05 #1
Share this Question
Share on Google+
17 Replies


P: n/a
>The fourth argument is a comparator that returns `an integer less than,
equal to, or greater than zero' depending on the ordering of its
arguments.

If I don't care about the order and simply want qsort() to run as
quickly as possible, how should the comparator be defined?
If you want it to run quickly, don't call qsort() at all.
If qsort were stable, the following would be best:

int
compare (void *x, void *y)
{
return 0;
}

...is this still true for a possibly non-stable qsort()?


Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.

Some versions of qsort() have been proven to misbehave badly
(e.g. smegmentation fault) if the comparison routine does not
provide a good ordering of the elements, requiring among
other things that
compar(a,b) == -compar(b,a)
and
compar(a,a) == 0
and
if compar(a,b) > 0 and compar(b,c) > 0, then compar(a,c) must be > 0

I am not sure whether qsort() walking off the end of the array if
compar() always returns 1 always violates the requirements of ANSI C
or not.

Gordon L. Burditt
Nov 14 '05 #2

P: n/a
Quoth Gordon Burditt on or about 2004-11-14:
Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.
I'm not actually calling qsort directly. I'm calling scandir; I figured
if I mentioned this I would be told `Go away, this is c.l.c, not
c.p.unix' :-)
Some versions of qsort() have been proven to misbehave badly


Blast. OT: is there an better function than scandir? I want a function
that takes the path of a directory and returns a list of names of files
it contains. I don't care how the list is ordered (hence the previous
question).

-trent
Nov 14 '05 #3

P: n/a
Trent Buck wrote:

Quoth Gordon Burditt on or about 2004-11-14:
Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.


I'm not actually calling qsort directly.
I'm calling scandir; I figured
if I mentioned this I would be told `Go away, this is c.l.c, not
c.p.unix' :-)


You don't like c.p.unix?

--
pete
Nov 14 '05 #4

P: n/a
Quoth pete on or about 2004-11-14:
if I mentioned this I would be told `Go away, this is c.l.c, not
c.p.unix' :-)


You don't like c.p.unix?


No, I've just never been there (or c.unix.p, silly me) -- and the
original question *was* about pure C. I'll toddle over there in a mo',
see what they have to say.

-trent
Nov 14 '05 #5

P: n/a
On Sun, 14 Nov 2004 08:15:15 GMT, in comp.lang.c , Trent Buck
<NO************@bigpond.com> wrote:
If I don't care about the order
Then why call qsort? Baffling remark !!
and simply want qsort() to run as
quickly as possible, how should the comparator be defined?
It has to be defined in such a way as to return an integer less than, equal
to or greater than zero, in order to indicate which of its arguments is to
be sorted first. Otherwise why bother calling it?
If qsort were stable, the following would be best:


(snip example of useless comparator)
This would be great, if you wanted qsort() to do nothing, possibly taking
infinite time to do it, possibly calling abort() after some implementation
defined loop or recurstion limit, possibly emitting the remark "I'm sorry
Dave, I can't do that..."
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Nov 14 '05 #6

P: n/a


Trent Buck wrote:
Quoth Gordon Burditt on or about 2004-11-14:
Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.

I'm not actually calling qsort directly. I'm calling scandir; I figured
if I mentioned this I would be told `Go away, this is c.l.c, not
c.p.unix' :-)

Some versions of qsort() have been proven to misbehave badly

Blast. OT: is there an better function than scandir? I want a function
that takes the path of a directory and returns a list of names of files
it contains. I don't care how the list is ordered (hence the previous
question).


Nothing OT to Standard C would support this.

<OFF-TOPIC>
You might consider function readdir along with opendir and closedir.
See:
http://www.cis.temple.edu/~ingargio/...adings/dired.c
for an example.
</OFF-TOPIC>

--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/

Nov 14 '05 #7

P: n/a
Quoth Al Bowers on or about 2004-11-14:
Blast. OT: is there an better function than scandir? I want a function Nothing OT to Standard C would support this.

Hm. Off and On both start with `O'.
You might consider function readdir along with opendir and closedir.

Thank you. I have now switched to open/read/closedir.

-trent
Nov 14 '05 #8

P: n/a
Mark McIntyre wrote:
On Sun, 14 Nov 2004 08:15:15 GMT, in comp.lang.c , Trent Buck
<NO************@bigpond.com> wrote:
If I don't care about the order


Then why call qsort? Baffling remark !!
and simply want qsort() to run as
quickly as possible, how should the comparator be defined?


It has to be defined in such a way as to return an integer less than,
equal to or greater than zero, in order to indicate which of its arguments
is to be sorted first. Otherwise why bother calling it?
If qsort were stable, the following would be best:


(snip example of useless comparator)
This would be great, if you wanted qsort() to do nothing, possibly taking
infinite time to do it, possibly calling abort() after some implementation
defined loop or recurstion limit, possibly emitting the remark "I'm sorry
Dave, I can't do that..."


An implementation of qsort() that has a problem with a comperator that
always returns 0 might have problems sorting "int a[] = {1, 1, 1};" with a
perfectly reasonable comperator. For a comperator that always returns 1,
I'd agree with you, but I'd expect qsort to be able to sort an array if
all elements compare equal.

Kurt Watzka

Nov 14 '05 #9

P: n/a
In article <20*********************@harpo.marx>,
Trent Buck <NO************@bigpond.com> wrote:
The fourth argument is a comparator that returns `an integer less than,
equal to, or greater than zero' depending on the ordering of its
arguments. If I don't care about the order and simply want qsort() to run as
quickly as possible, how should the comparator be defined?


How about comparing the pointers rather than the items pointed to? So
something like this:

int compare( void *x, void *y )
{
if ( x < y ) {
return -1;
}
else if ( y < x ) {
return 1;
}
else {
return 0;
}
}

Kevin Bagust.

Nov 14 '05 #10

P: n/a
kevin.bagust wrote:
In article <20*********************@harpo.marx>,
Trent Buck <NO************@bigpond.com> wrote:
The fourth argument is a comparator that returns `an integer less than,
equal to, or greater than zero' depending on the ordering of its
arguments.

If I don't care about the order and simply want qsort() to run as
quickly as possible, how should the comparator be defined?


How about comparing the pointers rather than the items pointed to? So
something like this:


Bad idea. qsort may change the position of elements even if they are
properly ordered, so comparing the pointer values may well be an
inconsistent comparator.

Always returning 0 need not eliminate the need to swap values for an
implementation of qsort (remember, qsort ist not even required to implement
quick sort) but at least qsort() should be able with an array of identical
elements. qsort() may fail in astounding ways if a < b and b < c does not
imply a < c.

Kurt Watzka
Nov 14 '05 #11

P: n/a
Trent Buck <NO************@bigpond.com> writes:
Quoth Gordon Burditt on or about 2004-11-14:
Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.


I'm not actually calling qsort directly. I'm calling scandir; I figured
if I mentioned this I would be told `Go away, this is c.l.c, not
c.p.unix' :-)


And one of scandir()'s arguments is a comparison function that's
passed to qsort().

The standard says nothing about the performance of qsort(). If you
pass it a comparison function that always returns 0, you'll get an
unspecified order, but there shouldn't be any problem. The only way
to tell whether this will be faster than using a non-trivial
comparison function is to measure it (or to analyze your system's
implementation of qsort() if you happen to have the source); the
results may or may not apply to any other system.

It would be probably useful for scandir to have a way to specify that
the array doesn't need to be sorted. <OT>On some systems, it
does.</OT>

--
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
kevin.bagust <ke**********@ntlworld.com> wrote in message news:<4d0dd8cff3ke**********@ntlworld.com>...
In article <20*********************@harpo.marx>,
Trent Buck <NO************@bigpond.com> wrote:
The fourth argument is a comparator that returns `an integer less than,
equal to, or greater than zero' depending on the ordering of its
arguments.
If I don't care about the order and simply want qsort() to run as
quickly as possible, how should the comparator be defined?


How about comparing the pointers rather than the items pointed to? So
something like this:

int compare( void *x, void *y )


int compare(const void *x, const void *y)
{
if ( x < y ) {
return -1;
}
else if ( y < x ) {
return 1;
}
else {
return 0;
}
}


Or...

#define UFO(x,y) (((y) < (x)) - ((x) < (y)))

int compare(const void *x, const void *y)
{
return UFO(x,y);
}

Trouble is, the standard states...

... The implementation may reorder elements of the array between
calls
to the comparison function, but shall not alter the contents of any
individual element.

There is nothing preventing qsort() from moving array elements in a
maner not determined by the comparison function, so long as the final
result meets the sort criteria.

Many sort implementations actually do this.[1]

AFAIK, it is not possible to make qsort() stable without encoding
original position information in the elements themselves, or having
the comparison function use a 'global' object recording pre-existing
positions.
[1]

% type stable.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define NELEM(x) (sizeof (x) / sizeof *(x))

int compare(const void *s, const void *t)
{
const char * const *u = s;
const char * const *v = t;
int cmp = strncmp(*u, *v, 3);
return cmp ? cmp : (u > v) - (u < v);
}

int main(void)
{
size_t i;
const char *array[] = { "aaa0", "aaa1", "aaa2", "aaa3", "aaa4",
"aaa5", "aaa6", "aaa7", "aaa8", "aaa9" };

fputs("before: ", stdout);
for (i = 0; i < NELEM(array); i++)
putchar(array[i][3]);
putchar('\n');

qsort(array, NELEM(array), sizeof *array, compare);

fputs(" after: ", stdout);
for (i = 0; i < NELEM(array); i++)
putchar(array[i][3]);
putchar('\n');

return 0;
}

% gcc -ansi -pedantic stable.c

% a.exe
before: 0123456789
after: 5123406789

%

--
Peter
Nov 14 '05 #13

P: n/a
Peter Nilsson wrote:
AFAIK, it is not possible to make qsort() stable without encoding
original position information in the elements themselves, or having
the comparison function use a 'global' object recording pre-existing
positions.


You can make qsort() stable, by using a stable
sorting algorithm like bubblesort or insertionsort.

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low;
unsigned char swap, *p1, *p2, *end;

if (nmemb-- > 1) {
array = base;
do {
low = array;
high = array += size;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}
--
pete
Nov 14 '05 #14

P: n/a
Quoth Keith Thompson on or about 2004-11-14:
The standard says nothing about the performance of qsort(). If you
pass it a comparison function that always returns 0, you'll get an
unspecified order, but there shouldn't be any problem. The only way
to tell whether this will be faster than using a non-trivial
comparison function is to measure it; the
results may or may not apply to any other system.


Thank you, this is what I had suspected. As I mentioned in another
reply, I have switched to using the opendir/readdir/closedir calls,
which are IIRC in POSIX.1.

-trent
Nov 14 '05 #15

P: n/a
On Sun, 14 Nov 2004 09:09:12 +0000, Gordon Burditt wrote:

....
If qsort were stable, the following would be best:

int
compare (void *x, void *y)
{
return 0;
}

...is this still true for a possibly non-stable qsort()?

yes
Wouldn't it be faster to not call qsort() at all in this
situation? You seem to be OK with having it not change anything.

Some versions of qsort() have been proven to misbehave badly
(e.g. smegmentation fault) if the comparison routine does not
provide a good ordering of the elements, requiring among
other things that
compar(a,b) == -compar(b,a)
and
compar(a,a) == 0
and
if compar(a,b) > 0 and compar(b,c) > 0, then compar(a,c) must be > 0
Always returning 0 creates a valid ordering relationship - all elements
compare equal, which is quite possible in real data.
I am not sure whether qsort() walking off the end of the array if
compar() always returns 1 always violates the requirements of ANSI C or
not.


Always returning 1 is invalid because compar(a,b) == -compar(b,a) is
violated. AFAICS always returning 0 is the only way to create a valid
comparison function without examining at the data.

Lawrence
Nov 14 '05 #16

P: n/a
Gordon Burditt wrote:
[...]
Some versions of qsort() have been proven to misbehave badly
(e.g. smegmentation fault) if the comparison routine does not
provide a good ordering of the elements, requiring among
other things that
compar(a,b) == -compar(b,a)


This is slightly stronger than the actual requirement:
only the signs of the compar() values are relevant, not
their magnitudes. compar(a,b) == 1 && compar(b,a) == -42
would work just fine.

--
Er*********@sun.com

Nov 14 '05 #17

P: n/a

On Mon, 15 Nov 2004, pete wrote:

Peter Nilsson wrote:
AFAIK, it is not possible to make qsort() stable without encoding
original position information in the elements themselves, or having
the comparison function use a 'global' object recording pre-existing
positions.


You can make qsort() stable, by using a stable
sorting algorithm like bubblesort or insertionsort.


If you use your own stable-sorting algorithm, you are no longer using
'qsort', the standard library function Peter was talking about. (He was
speaking from the programmer's point of view, not the implementor's.)

-Arthur
Nov 14 '05 #18

This discussion thread is closed

Replies have been disabled for this discussion.