int partition(vector<int> &A, int i, int j, int x)
{
while(1)
{
while (j >= i && A[j] >= x)
j--;
while (A[i] < x)
i++;
if (i < j)
swap(A[i],A[j]);
else
return j;
}
}
void quicksort(vector<int> &A, int i, int j)
{
if (i == j) return;
int k = partition(A,i,j,A[i]);
if (k < i)
k = i;
quicksort(A,i,k);
quicksort(A,k+1,j);
}
When we tested this on random arrays of integers we found that
it was pretty fast. Certainly it didn't behave like
quicksort's worst case running time, which is Θ(n^2).
This leads us to the hypothesis that quicksort's average
running time is closer to its best-case, which is
Θ(n lg n).
- Let p(n) be the time required for partition on a range of n values. Since p(n) = Θ(n), there is a constant b such that p(n) ≤ b n.
- Let T(n) be the expected value of quicksort's running time on a range of elements (i.e. the average case runnig time). T(n) is what we're trying to determine! Since we've already determined that the best case time is Θ(n lg n) we have T(n) = Ω(n lg n). What we want to prove here is that T(n) = O(n lg n), which would then show T(n) = Θ(n lg n).
- We make the inductive hypothesis that a is a constant such that T(m) ≤ a m lg m when 1 < m < n, with the additional constraints that a ≥ 2 T(1) and a ≥ 8 b. Note that T(2) ≤ a 2 lg 2 is trivially true, which gives a base case for the inductive proof.
-
Proposition: Given the inductive hypothesis
T(1) + T(n-1) ≤ a n lg n - a/2.
Proof:
T(1) ≤ a/2
T(n-1) ≤ a (n-1) lg(n-1) ≤ a (n-1) lg n ≤ a n lg n - a lg n ≤ a n lg n - a
T(1) + T(n-1) ≤ a/2 + a n lg n - a ≤ a n lg n - a/2. -
Proposition:
Given the inductive hypothesis
T(k) + T(n-k) ≤ a n lg n - a k, where 2 ≤ k ≤
[n/2]. Note: "[ ]" will be used to denote "floor".
Proof:
T(k) + T(n-k) ≤ a k lg k + a(n-k) lg(n-k) ≤ a k lg(n/2) + a (n-k) lg n, since k ≤ n/2 and n-k ≤ n ≤ a k (lg n - lg 2) + a (n-k) lg n ≤ a k lg n - a k + a (n-k) lg n ≤ a lg n(k + n-k) - a k ≤ a n lg n - a k -
Using the above definitions, propostitions and the
inductive hypothesis, we will show that T(n) ≤ a n lg n.
To do this, we use the definition of expected value: The
expected value is the sum of the probability of each event
times the value of that event. In our terms, the sum of
the probability of each partition size times the expected
time of quicksort given that partition size. The possible
sizes from partition are (0,n), (1,n), (2,n), ...,
(n-1,1). With random data, each parition result occurs
with probability 1/n. There is one assumption that we'll
need to make:
Assumption: We assume that the expected time required for quicksort on input A,i,j is the same for a range i,j of random values as for a range i,j that resulted from a call to partition. I.e. partition preserves randomness in each of the partitions it returns.
Quicksort calls partition, then recursively calls itself on the two partition sets, possibly correcting for the empty partition as discussed in class. So we will sum up the total work for quicksort on a range of n elements and determine that it is less than or equal to a n lg n as follows:
