From: gomskams@yahoo.co.uk (goms)
Subject: Quick Sort Median of Three worst case
Date: 30 Jan 2003 14:25:49 -0800
Date: 2003-01-30T22:25:49+00:00 [thread overview]
Message-ID: <588d8bf4.0301301425.586b0ae4@posting.google.com> (raw)
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.
next reply other threads:[~2003-01-30 22:25 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-01-30 22:25 goms [this message]
2003-01-30 23:51 ` Quick Sort Median of Three worst case Bobby D. Bryant
2003-01-31 12:28 ` Marin David Condic
2003-01-31 9:17 ` Wendy E. McCaughrin
2003-01-31 9:59 ` Albert van der Horst
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox