Quicksort

Description of quicksort

1. Quicksort, like merge sort, applies the divide-and-conquer paradigm

2. The following procedure implements quicksort:

   QUICKSORT（A,p,r） 
   if p<r 
   	q = PARTITION（A, P,r）
   	QUICKSORT（A, P,q-1） 
   	QUICKSORT（A,q+1,r）

   To sort an entire array A, the initial call is QUICKSORT(A,1,A.length)

3. The key to the algorithm is the PARTITION procedure

   PARTITION（A, P,r） 
   x = A[r]
   i=p-1
   for j=p to r-1
   	if A[j] ≤ x
   		i=x+1
   		exchange A[i] with A[j]
   exchange A[j+1] with A[r]
   return i+1

   PARTITION always selects an element x = A[r]as a pivot element around which to partition the subarray A[p..r]

Performance of quicksort

1. The running time of quicksort depends on whether the partitioning is balanced or unbalanced, which in turn depends on which elements are used for partitioning.
2. If the partitioning is balanced, the algorithm runs asymptotically as fast as merge sort. . If the partitioning is unbalanced, however, it can run asymptotically as slowly as insertion sort.
3. Worst-case partitioning
   • The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with n-1 elements and one with 0 elements.
   • use the substitution method to prove that the recurrence has the solution
4. Best-case partitioning
   • In the most even possible split, PARTITION produces two subproblems, each of size no more than n/2.
   • By case 2 of the master theorem, this recurrence has the solution
5. Balanced partitioning
   • The average-case running time of quicksort is much closer to the best case than to the worst case.
   • Intuitively,The running time is

A randomized version of quicksort

Instead of always using as the pivot, we will select a randomly chosen element from the subarray .We do so by first exchanging element with an element chosen at random from .

RANDOMIZED-PARTITION(A,p,r)
1 = RANDOM(p,r)
exchange A[r] with A[i]
return PARITITION(A,p,r)

The new quicksort calls RANDOMIZED-PARTITION in place of PARTITION:

RANDOMIZED-QUICKSORT(A,p,r)
if p<r
	q = RANDOMIZED-PARTITION(A,p,r)
	RANDOMIZED-QUICKSORT(A,p,q-1)
	RANDOMIZED-QUICKSORT(A,q+1,r)

Analysis of quicksort

Worst-case analysis

Let be the worst-case time for the procedure QUICKSORT on an input of size . We have the recurrence We guess that for some constant . Substituting this guess into recurrence, we obtain then when , ,decreasing in the beginning of the interval and increasing in the end, which means that those two points are the only candidates for a maximum in the interval.

Continuing with our bounding of , we obtain Thus,

Expected running time

Lemma: Let be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an -element array. Then the running time of QUICKSORT is Proof:,the algorithm makes at most n calls to PARTITION(Each time the PARTITION procedure is called, it selects a pivot element, and this element is never included in any future recursive calls to QUICKSORT and PARTITION.), each of which does a constant amount of work and then executes the for loop some number of times. Each iteration of the for loop executes line 4.

We first observe that each pair of elements is compared at most once. Elements are compared only to the pivot element and, after a particular call of PARTITION finishes, the pivot element used in that call is never again compared to any other elements.

We define the set to be the set of elements between and , inclusive.

We define

Since each pair is compared at most once, we can easily characterize the total number of comparisons performed by the algorithm: Taking expectations of both sides, and then using linearity of expectation and Lemma 5.1, we obtain Combining equations: We can evaluate this sum using a change of variables () and the bound on the harmonic series in equation: Thus we conclude that, using RANDOMIZED-PARTITION, the expected running time of quicksort is when element values are distinct.