Quick Sort

Algorithm

proc quick-sort(A, p, r)
	if p < r then
		q = partition(A, p, r)
		quick-sort(A, p, q-1)
		quick-sort(A, q+1, r)
func partition(A, p, r)
	x = A[r]
	i = p-1
	for j = p to r-1 do
		if A[j] < r then
			i = i + 1
			A[i] <-> A[j]
	A[i+1] <-> A[r]
	return i+1

Comparisons

For the worst case, the list is already sorted.

For the best case, partitions are equally sized.

For the average case, we can approximate with a reccurence:

The exact reccurence is:

T(n)={0ifn=1(n1)+Σq=1n(1n)(T(q1)+T(nq))otherwise

The closed form solution (through constructive induction) is: 1.39nlgn.

Another more clever argument can be used to get the exact answer without the difficult reccurence. Consider elements i and j such that i<j. Consider choice of pivot k:

  1. If k<i this has no effect.
  2. If k=i the elements are compared.
  3. If i<k<j the elements aren’t compared.
  4. If k=j the elements are compared.
  5. If j<k this has no effect.

We just sum the probability that each pair is compared to one another: