Re: QuickSort (worst-cases... special data)

On 5 Maj, 22:48, t...@xxxxxxxxxxxxxxxxxxxx (Tom Truscott) wrote:
I've got a problem with QuickSort's analysis.
The worst-case complexity is O(n^2) and in my analys I have data
generated in that way...
I think it is called A-shape and Vshape sequences...

The worst-case sequence depends on how quicksort selects the pivot.

If it uses median-of-1st,last,middle then both A and V should be equally bad.
Some quicksorts use the median of e.g. 9 elements, or choose "randomly".
That is still worst-case O(N^2) but not for the simple A and V patterns.

There is a worst-case O(N) median algorithm,
and a quicksort that uses it can be worst-case O(NlgN).

Tom Truscott

I see i forgot to write that i have to choose always middle element
and both sequences have bad timings, but V is much better than A...
but they are still O(n^2) but different... so again, what can cause it?
.

Relevant Pages

  • Re: Quicksort pathological behavior?
    ... > - Pivot selection is always the middle element of the subarray, ... > numbers of equal elements in the array. ... > Can someone more familiar with the algorithm than I am tell me if the ... something can foul up quicksort. ...
    (comp.programming)
  • Re: Whats the best language to learn...
    ... For example, quicksort is O, ... is unambiguous and not subject to modifiers. ... perfectly well refer to worst case, mean, or any specific case you want. ... It's a mathematical statement about a sequence: ...
    (comp.programming)
  • Re: Fastcode Sort: Combsort
    ... >"Although the original comb sort generally works well, ... Re "killer sequences", my main testing in that regard has been at ... Most of the quicksort variants I have on file and been ... I generate a sorted sequence of numbers. ...
    (borland.public.delphi.language.basm)
  • Re: QuickSort (worst-cases... special data)
    ... I think it is called A-shape and Vshape sequences... ... The worst-case sequence depends on how quicksort selects the pivot. ... There is a worst-case Omedian algorithm, ...
    (comp.theory)