Re: Quicksort


<robertwessel2@xxxxxxxxx> wrote in message
news:995646df-36cb-469e-a992-7b167371b9c4@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jan 8, 4:58 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
"robertwess...@xxxxxxxxx" wrote:
CBFalconer <cbfalco...@xxxxxxxxx> wrote:

Stack size is unavoidably a problem with the fully recursive
version, unless, of course you can afford order N stack space.

Or your compiler guarantees to do tail-recursion elimination.

That won't normally control the recursion depth, since each level
has to depend on the relative size of the segments. It is
trivially easy to do it yourself, and ensure the depth never
exceeds ln2(size).

If you recurse in the correct order (smaller partition first),
and the compiler does tail recursion elimination for the second
(larger) partition, you will use no more than log(n) stack space.
Basically what's happening is that the compiler converts the
fully recursive form to the semi recursive form of quicksort by
looping on the second (larger) partition.

Write out the code and see the problem for yourself.


OK:

quicksort(partition p)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
quicksort(largepart)
}

What problem? If the compiler does tail recursion elimination, the
second recursive call is turned into a loop, and the only growth in
stack size happens when the smaller partition is recursively sorted,
which trivially ensures a limit of log(n) stack usage.

IOW, tail recursion elimination allows the compiler to convert the
above into the explicitly semi-recursive version of quicksort:

quicksort(partition p)
{
loop while ((size of p) > 1)
{
leftpart,rightpart=partition(p)
smallpart,largepart=orderbysize(leftpart,rightpart)
quicksort(smallpart)
p=largepart
}
}

If the compiler does *not* do tail recursion elimination, stack usage
is proportional to n in the worst case. Given that most compiler
don't actually do tail recursion elimination, and many of the ones
that do don't provide strong guarantees as to when it happens, a fully
recursive quicksort implementation (as first pseudocode sample) should
almost always be considered flawed.

oh, this shows, something...
....
....


how about we stick to actual code (exact lang doesn't matter so much
probably...).
then we can actually debate about what will actually happen, rather than
pcode written in forms that will lead to little more than conjecture and
idle speculation wrt the underlying implementation...

abstact for abstract, concrete for concrete.
not so sensible to use the abstract and then debate about points in the
concrete.


now, IMO, the points of debate are this:
quicksort, in a purely recursive form, likes to overflow if nothing is done;
quicksort, in some edge cases, gets bad performance;
quicksort, in the average case, is one of the fastest sort algos.

highest priority here: overflows.
not good to have the app crash, after all.

so, my approach: on overflow fall back to a different sort (typically a
simple but slow sort).

pros:
complexity is avoided;
the input sets that are problematic for quicksort, tend to be fairly
specific, and thus, on average, can be effectively handled by a good
selection for the slow sorter;
even as such, bad cases are rare enough, that it is not a serious problem
(O(n^2) is bad, but not often a show-stopper).

cons:
being as such, a tradeoff approach (as are algo choices in general), the
theoretical worst case is still O(n^2), and the performance still depends
somewhat on the input set;
some here debate the arbitrary use of a fallback at a certain recursion
depth.


heapsort:
this is proposed as a replacement for quicksort by some posters here.

pros:
does not overflow;
is fairly consistent wrt times, and has an O(n log2 n) worst case.

cons:
its average case performance, though not terrible, is not very good either;
by itself, it is more complicated than quicksort (and way more than the
various O(n^2) options).


introsort:
a theoretically better option, quicksort with a heapsort fallback.

pros:
general case, full speed of quicksort, with an O(n log2 n) worst case.

cons:
one then has the combined complexity of both quicksort and heapsort, making
it less practical to copy and specialize for each use case.


the common approach used for library based sort functions, aka, a "generic
array", and a callback compare function, is expensive.

hypothetical example, we have a sort function O(n log2 n), that operates in
an otherwise very inefficient manner, and an O(n^2) sort (say, a highly
specialized selection sort).

which is better depends on the relative overhead (the O(1)/O(1) between the
algos).


this overhead is bound:
consider, 1k items, log2(1000) => 9.97, so:
O(n log2 n) is approx O(10000)
O(n^2) is O(1000000)
1000000/10000 => 100

so, if a 100x slowdown exists, the O(n^2) algo may well be faster.

for 100 items:
log2(100) => 6.64
O(n log2 n) is approx O(664)
O(n^2) is O(10000)
10000/664 => 15.06

so, if a 15x slowdown exists, the O(n^2) algo may well be faster.

much smaller, and it may well be faster to just use something like sel-sort.


templates, though one way of dealing with the above problem, are not
available in C (and using macros in this case is just horrid).

....


so, it is my view of the problem, that in general quicksort is a better
option for general purpose sorting (for moderate or larger data sets),
introsort is better if it is reasonable to implement or reuse it in the
specific context, and there are still many cases where cocktail sort, bubble
sort, and selection sort are very reasonable options.

after all, there are many cases where the running time of cocktail sort
approaches O(n), and if we know that these cases are particularly common,
then there is good reason to choose this algo.


IMO, heapsort is good, if the O(n^2) worst case of quicksort would be
unacceptable, and at the same time intosort would be unreasonable.


however, most of the time, we will encounter the problem, write a solution,
and very likely not think much of it again (if ever).


after all, in code, the only real aspect of performance that really matters,
is if it is fast enough...

or, alternatively, optimizing via the profiler...



.