quicksort


QuicksortMathworldPlanetmath is a divide-and-conquer algorithmMathworldPlanetmath for sorting in the comparison model. Its expected running time is O(nlgn) for sorting n values.

Algorithm

Quicksort can be implemented recursively, as follows:

Algorithm Quicksort(L)
Input: A list L of n elements
Output: The list L in sorted order
if n>1 then
          p random element of L

A{x|xL,x<p}

B{z|zL,z=p}

C{y|yL,y>p}

SAQuicksort(A)

SCQuicksort(C)

return Concatenate(SA,B,SC)
else
          return L

Analysis

The behavior of quicksort can be analyzed by considering the computation as a binary treeMathworldPlanetmath. Each node of the tree corresponds to one recursive call to the quicksort procedure.

Consider the initial input to the algorithm, some list L. Call the Sorted list S, with ith and jth elements Si and Sj. These two elements will be compared with some probability pij. This probability can be determined by considering two preconditions on Si and Sj being compared:

  • Si or Sj must be chosen as a pivot p, since comparisons only occur against the pivot.

  • No element between Si and Sj can have already been chosen as a pivot before Si or Sj is chosen. Otherwise, would be separated into different sublists in the recursion.

The probability of any particular element being chosen as the pivot is uniform. Therefore, the chance that Si or Sj is chosen as the pivot before any element between them is 2/(j-i+1). This is precisely pij.

The expected number of comparisons is just the summation over all possible comparisons of the probability of that particular comparison occurring. By linearity of expectation, no independence assumptions are necessary. The expected number of comparisons is therefore

i=1nj>inpij = i=1nj>in2j-i+1 (1)
= i=1nk=2n-i+12k (2)
2i=1nk=1n1k (3)
= 2nHn=O(nlgn), (4)

where Hn is the nth Harmonic number.

The worst case behavior is Θ(n2), but this almost never occurs (with high probability it does not occur) with random pivots.

Title quicksort
Canonical name Quicksort
Date of creation 2013-03-22 13:59:19
Last modified on 2013-03-22 13:59:19
Owner thouis (3290)
Last modified by thouis (3290)
Numerical id 13
Author thouis (3290)
Entry type Definition
Classification msc 68P10
Related topic SortingProblem