Quicksort quickie

I've just been looking at SortedCollection>>quicksortFrom:to: in an effort
to circumvent some unexpectedly severe performance problems with sorting.  I
believe that the test which is commented:

  "Recursively sort larger sub-interval and process smaller remainder on the
next loop iteration"

is the wrong way around -- the idea should be to recurse into the *smaller*
collection and iterate into the larger one.  Otherwise you run out of stack
space on even moderately pathological cases.

    -- chris

P.S.  I did fix my problem, a mixture of turning on the newer sort
implementation, adding the above fix, and using < instead of <= in the
comparison (I had a lot of equal keys).

Chris

You wrote in message
news:[hidden email]...
> I've just been looking at SortedCollection>>quicksortFrom:to: in an effort
> to circumvent some unexpectedly severe performance problems with sorting.
I
> believe that the test which is commented:
>
>   "Recursively sort larger sub-interval and process smaller remainder on
the
> next loop iteration"
>
> is the wrong way around -- the idea should be to recurse into the
*smaller*
> collection and iterate into the larger one.  Otherwise you run out of
stack
> space on even moderately pathological cases.

Yes, common sense would suggest that, however that is the way the algorithm
is defined in the book referenced by the method comment. We'll look into it
(defect no. 238).

Regards

Blair

Blair,

> Yes, common sense would suggest that, however that is the way the
algorithm
> is defined in the book referenced by the method comment. We'll look into
it
> (defect no. 238).

Yes, the book has it wrong.  They claim to be following Knuth, who does the
same thing!  To be fair they are both using an explicit "stack", so it's not
as important, but still...!  They also reference Sedgewick who does get it
right.

You may be interested in the newish "introsort" algorithm which is
apparently taking the C++ STL implementation world by storm.  Its basically
a median-of-three quicksort which switches to heapsort (or anything else
with a good worst-case) when it detects that quicksort seems to be going
O(N^2).

It was described in:

    David R. Musser, Introspective Sorting and Selection Algorithms
    Published in Software--Practice and Experience, (8): 983-993 (1997)

which can be found online via

    http://www.cs.rpi.edu/~musser/gp/index_1.html

> Blair

    -- chris

Chris

You wrote in message news:9ffvtu$61$[hidden email]...
> Blair,
>
> > Yes, common sense would suggest that, however that is the way the
> algorithm
> > is defined in the book referenced by the method comment. We'll look into
> it
> > (defect no. 238).
>
> Yes, the book has it wrong.  They claim to be following Knuth, who does
the
> same thing!  To be fair they are both using an explicit "stack", so it's
not
> as important, but still...!  ...

Well its just as important really, since their explicit stack is still of a
fixed size. One can control the size of the stacks in Dolphin (though to do
so involves either modifying the default maximum size, or explicitly
creating a process with a larger potential stack), so it amounts to much the
same thing.

>...They also reference Sedgewick who does get it
> right.

Gonnet & Baeza-Yates' "Handbook of Algorithms & Data Structures" also gets
it right by sorting the smaller partition recursively.

>
> You may be interested in the newish "introsort" algorithm which is
> apparently taking the C++ STL implementation world by storm.  Its
basically
Thanks for the reference. Perhaps in a spare moment....

Regards

Blair