hello everybody , this is exercise 7-5 of CLRS i just need to match
my answers .............
can anyone help me
One way to improve the RANDOMIZED-QUICKSORT procedure is to partition
around a
pivot that is chosen more carefully than by picking a random element
from the subarray. One
common approach is the median-of-3 method: choose the pivot as the
median (middle
element) of a set of 3 elements randomly selected from the subarray.
(See Exercise 7.4-6.) For
this problem, let us assume that the elements in the input array A[1
n] are distinct and that n
≥ 3. We denote the sorted output array by A'[1 n]. Using the median-
of-3 method to choose
the pivot element x, define pi = Pr{x = A'[i]}.
a
Give an exact formula for pi as a function of n and i for i = 2,
3,..., n - 1. (Note that p1
= pn = 0.)
b
. By what amount have we increased the likelihood of choosing the
pivot as x = A'[⌊(n
+ 1/2⌋], the median of A[1 n], compared to the ordinary
implementation? Assume
that n → ∞, and give the limiting ratio of these probabilities.
c. If we define a "good" split to mean choosing the pivot as x =
A'[i], where n/ ≤ i ≤ 2n/3,
by what amount have we increased the likelihood of getting a good
split compared to
the ordinary implementation? (Hint: Approximate the sum by an
integral.)
d. Argue that in the Ω(n lg n) running time of quicksort, the median-
of-3 method affects
only the constant factor.
thanks in advance
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
