Quick Sort Median of Three worst case

Quick Sort Median of Three worst case

[goms]

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.

Re: Quick Sort Median of Three worst case

[Bobby D. Bryant]

On Thu, 30 Jan 2003 14:25:49 -0800, goms wrote:

> A reply with explanation will be great.  Thanks in Advance.

Algorithms class?

-- 
Bobby Bryant
Austin, Texas

Re: Quick Sort Median of Three worst case

[Marin David Condic]

Bobby D. Bryant <bdbryant@mail.utexas.edu> wrote in message
news:pan.2003.01.30.23.51.02.483076@mail.utexas.edu...
> On Thu, 30 Jan 2003 14:25:49 -0800, goms wrote:
>
> > A reply with explanation will be great.  Thanks in Advance.
>
> Algorithms class?
>

And worse, it isn't even an Ada question so it has no relevance to this
group - or the ones it was cross-posted to.

MDC
--
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

    "I'd trade it all for just a little more"
        --  Charles Montgomery Burns, [4F10]
======================================================================

Re: Quick Sort Median of Three worst case

[Wendy E. McCaughrin]

In comp.lang.c 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) ?

 It depends upon what is meant by "running time". QuickSort basically has to
 perform three operations at each iteration/recursion: selection of a pivot,
 comparison of elements to the pivot from its left and right, and transposi-
 tions when out of order. 
 In (a), the first iteration would (using Median of 3) choose 2, 1, N/2 and
 choose N/2 as the pivot, then compare 2 and 1 to it and transpose them, and 
 then compare about N/2 - 1 remaining elements left of the pivot to it, only
 to find them in sort.  Thus no more transpositions in that first iteration
 would occur, and no further transpositions would occur in future iterations.
 But pivots would still get chosen and comparisons of elements made against 
 it, so it appears that O(n*lg(n)) comparisons would occur. (The common case
 of QuickSort said to perform O(n^2) on nearly-sorted lists is an artifact of
 always choosing some minimum or maximum element from the left or right on
 each partition.)

 In (b), the first transposition is avoided but -- since every element com-
 pared to the pivot would be out of sort, the number of transpositions as
 well as comparisions appears to be O(n*lg(n)).

 In both cases -- since Median of 3 is used to select the pivot from sorted
 lists -- the pivot manages to bisect the least into two equal halves, thus
 helping to ensure O(lg(n)) iterations from original list to smallest parti-
 tion.

Re: Quick Sort Median of Three worst case

[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