449,264 Members | 1,763 Online
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
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 itsarguments.If I don't care about the order and simply want qsort() to run asquickly 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 wrote: If I don't care about the order Then why call qsort? Baffling remark !! and simply want qsort() to run asquickly 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 CLC readme: ----== 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 thissituation? 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. You might consider function readdir along with opendir and closedir. See: http://www.cis.temple.edu/~ingargio/...adings/dired.c for an example. -- 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 wrote:If I don't care about the order Then why call qsort? Baffling remark !!and simply want qsort() to run asquickly 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 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 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 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. On some systems, it does. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 14 '05 #12

 P: n/a kevin.bagust wrote in message news:<4d0dd8cff3ke**********@ntlworld.com>... In article <20*********************@harpo.marx>, Trent Buck 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 #include #include #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.