Re: Quick Sort Median of Three worst case

[albert@spenarnc.xs4all.nl (Albert van der Horst)]

In article <588d8bf4.0301301425.586b0ae4@posting.google.com>,
goms <gomskams@yahoo.co.uk> wrote:
>Hi,
>
>I would like to know the running time of the Median of Three routine
>version Quick Sort for the following input
>
>(a)      2, 3, 4, ..,N-1, N, 1
>
>What is the running time for the following input
>
>(b)      1, N, N-1, ....., 4, 3, 2
>
>Is the above said inputs (a) and (b) the worst case? and is the
>running time is O(N^2) ?
>
>I know that using Median of Three routine version of Quick Sort for,
>
>a) sorted input
>  the pivot is always in the middle, so the time would be O(nlogn)
>
>b) reverse-ordered input
>  the pivot is always in the middle, so the time would be O(nlogn)
>
>
>A reply with explanation will be great.  Thanks in Advance.

Your questions cannot be answered because they are critically
dependant on implementation details. However I can offer the
following explanation:

The worst case for a simplistic qsort is O(N^2) (where the pivot
happens to be the minimum of the remainder to be sorted.)
(This has actually occurred on sorted sets, where the first element
is chosen as a pivot.)
On a very contrived data set the Median of Three would result
in a pivot that is the second minimum item of the remainder to be
sorted.) This too would be be O(N^2).

Some qsorts use random selection for the pivot.
The data set would need to be contrived for exactly the RNG and
the random seed, but it is still possible.
Extremely unlikely, but present as a worst case.
QED

--
-- 
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
Q.: Where is Bin? A.: With his ma. Q.: That makes the Saudi's
terrorists, then?  A.: No, George already owns their oil.
albert@spenarnc.xs4all.nl     http://home.hccnet.nl/a.w.m.van.der.horst