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

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
.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... Possibility here that such sequences exist is 100%, but probability that tihi happend in practice is very low. ... That is exactly my point why original Hoare's Quicksort should be avoided. ... With "middle element pivot" on alredy sorted array situation is a bit differen. ... - Modified Radix to support integers. ...
    (borland.public.delphi.language.basm)
  • Re: Help needed for a sorting code in the literature
    ... > Over the last few days I have been playing with pure heapsort, ... > quicksort and introsort (quicksort core with insertion sort for small ... > blocks and heapsort for high recursion depth). ... problem is the distribution of the sequences being sorted. ...
    (sci.crypt)
  • Re: Parallel quicksort Question
    ... The performances of my parallel program ... Quicksort can be used for merging, ... Your quicksort uses the last element as pivot value for partitioning. ... Within already presorted sequences this is either a very small or very big value. ...
    (comp.parallel.mpi)
  • Re: QuickSort (worst-cases... special data)
    ... The worst-case sequence depends on how quicksort selects the pivot. ... There is a worst-case Omedian algorithm, ... I see i forgot to write that i have to choose always middle element ...
    (comp.theory)
  • Re: question on sorting algorithms
    ... > for sequences with many repeating elements. ... Never mind my caffeine-deficient ramblings about Quicksort in my ... of comparisons in the partitioning phase, ...
    (comp.programming)