Reversing order of quicksort

[flipflop]

Martin Dickopp <ex****************@zero-based.org> wrote in message news:<cu*************@zero-based.org>...

is there
any particular reason why you cannot or don't want to use the `qsort'
function in the standard C library?
I'm using gcc on mingw and assumed it was so minimal it wouldn't
include it. Should've checked because it does of course.
As to your question, just invert all comparisons of the elements to be
sorted. For example,

while (item[i]>x && i<right) i++;
while (x>item[j] && j>left) j--;

should become

while (item[i]<x && i<right) i++;
while (x<item[j] && j>left) j--;

Thanks very much - I couldn't quite see what to invert and what to
leave alone. That works perfectly.

[David Mathog]

On 28 May 2004 06:55:19 -0700
fl******@easy.com (flipflop) wrote:

Martin Dickopp <ex****************@zero-based.org> wrote in message news:<cu*************@zero-based.org>...

is there
any particular reason why you cannot or don't want to use the `qsort'
function in the standard C library?

I'm using gcc on mingw and assumed it was so minimal it wouldn't
include it. Should've checked because it does of course.

There's a very good reason not to use the built in qsort functions -
much better performance can be achieved by using a custom built quicksort routine that doesn't pass the
comparison as a pointer to a function. If your
program is rate limited by the sort function the overhead in that
method can result in a >2X speed difference. For instance, on an
Athlon MP2000 sorting a 10M cell integer array with gcc 3.3.3 qsort
takes 6.4 seconds but using my own quicksort, with integer comparison
built in (not a function call), it runs in 2.7 seconds. The ratio
is similar for other small data types and only approaches 1x when
comparing large or complex data types (ie, much more time in the comparison function than in the function call overhead).

That said, very few programs I've encountered are rate limited by sorts,
and the builtin qsort is more convenient in that you don't need a different qsort for each data type sorted, just a different comparison
function (which is typically small and easy to write). If your program
is only spending 2% of its time sorting then doubling the sorting speed
will only speed up the program by 1%, which is pretty negligible.

Regards,

David Mathog
ma****@caltech.edu
Manager, Sequence Analysis Facility, Biology Division, Caltech

[Robert Wessel]

David Mathog <ma****@caltech.edu> wrote in message news:<20040528082405.5a781700.ma****@caltech.edu>. ..

There's a very good reason not to use the built in qsort functions -
much better performance can be achieved by using a custom built quicksort routine that doesn't pass the
comparison as a pointer to a function. If your
program is rate limited by the sort function the overhead in that
method can result in a >2X speed difference. For instance, on an
Athlon MP2000 sorting a 10M cell integer array with gcc 3.3.3 qsort
takes 6.4 seconds but using my own quicksort, with integer comparison
built in (not a function call), it runs in 2.7 seconds. The ratio
is similar for other small data types and only approaches 1x when
comparing large or complex data types (ie, much more time in the comparison function than in the function call overhead).

That said, very few programs I've encountered are rate limited by sorts,
and the builtin qsort is more convenient in that you don't need a different qsort for each data type sorted, just a different comparison
function (which is typically small and easy to write). If your program
is only spending 2% of its time sorting then doubling the sorting speed
will only speed up the program by 1%, which is pretty negligible.

While this is all perhaps true, the OP's implementation is quite poor
(fully recursive, no median-of-three, uses Quicksort even on tiny
partition, etc.). Assuming it runs at all (eg. no stack overflow on
largish inputs), it'll probably get trashed performance-wise by the C
library routine, despite the overhead of the indirect call to the
comparison function.