Re: Quicksort

On Jan 8, 8:12 pm, "cr88192" <cr88...@xxxxxxxxxxx> wrote:
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.


Of course, the particular point being addressed was about the
algorithm, not a particular implementation, but whatever...


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).


(...options snipped...)

While a fallback to a O(n**2) sort is not an unreasonable way to avoid
the excessive stack growth, just fixing the implementation of
quicksort to avoid the excessive stack growth is almost certainly
simpler - that's one of my major points.

Also, I'd argue that an unexpected 50000x increase in runtime may well
be equivalent to having the application crash (the approximate factor
if a quicksort of a million elements goes quadratic).


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.


While that's theoretically true, it's also fairly far divorced from
reality. Typical implementations of heapsort have an average runtime
of about double that of quicksort, and in the case of heapsort, that's
also approximately the maximum run time.

In any event, for 1000 elements, this is all a pretty much pointless
debate. If you only got a few thousand elements to sort, use
Shellsort - it's simpler, and at approximate O(n**1.5) worst case is
almost always good enough for such small data sets. You might even
want to consider that for the quicksort fallback.

But your point that performance needs to be "good enough" is correct -
which is why heapsort is very attractive. It's only marginally slower
than quick sort, and will never bite you in the posterior by going
quadratic. IOW, if it's good enough, it will alwyas be good enough,
no surprised - the same cannot be said of quicksort, even though it
may be a bit better on average.
.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Quicksort
    ... version, unless, of course you can afford order N stack space. ... fully recursive form to the semi recursive form of quicksort by ... If the compiler does tail recursion elimination, ... quicksort, in the average case, is one of the fastest sort algos. ...
    (comp.programming)
  • Re: Quicksort
    ... >>> quicksort, in the average case, is one of the fastest sort algos. ... of the kind found in qsort. ... > with compiler optimizations, qsort is still about 1.3x faster than> heapsort. ...
    (comp.programming)
  • Re: Quicksort
    ... quicksort, in a purely recursive form, likes to overflow if nothing is ... quicksort, in the average case, is one of the fastest sort algos. ... of about double that of quicksort, and in the case of heapsort, that's ... of the kind found in qsort. ...
    (comp.programming)
  • Re: Premiership managers who refuse to talk to the BBC
    ... There are perhaps half a dozen clever, thoughtful, well-adjusted adults ... you can't get that sort of depth from this group anymore. ... There is deeper and more interesting debate to be had in other fora ...
    (uk.media.tv.misc)