PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
quicksort (Definition)

Quicksort is a divide-and-conquer algorithm for sorting in the comparison model. Its expected running time is $ O(n\lg n)$ 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
$\textstyle \parbox{\textwidth}{ $p \gets \mbox{ random element of } L$\ $A \g... ...sort(A)$\ $S_C \gets Quicksort(C)$\ {\bf return} $Concatenate(S_A,B,S_C)$ }$
else
$\textstyle \parbox{\textwidth}{{\bf return} $L$}$

Analysis

The behavior of quicksort can be analyzed by considering the computation as a binary tree. 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 $ i$th and $ j$th elements $ S_i$ and $ S_j.$ These two elements will be compared with some probability $ p_{ij}$. This probability can be determined by considering two preconditions on $ S_i$ and $ S_j$ being compared:

  • $ S_i$ or $ S_j$ must be chosen as a pivot $ p$, since comparisons only occur against the pivot.
  • No element between $ S_i$ and $ S_j$ can have already been chosen as a pivot before $ S_i$ or $ S_j$ 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 $ S_i$ or $ S_j$ is chosen as the pivot before any element between them is $ 2/(j-i+1)$. This is precisely $ p_{ij}.$

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


$\displaystyle \sum_{i=1}^{n}\sum_{j>i}^{n}p_{ij}$ $\displaystyle =$ $\displaystyle \sum_{i=1}^{n}\sum_{j>i}^{n}\frac{2}{j-i+1}$ (1)
  $\displaystyle =$ $\displaystyle \sum_{i=1}^{n}\sum_{k=2}^{n-i+1}\frac{2}{k}$ (2)
  $\displaystyle \le$ $\displaystyle 2\sum_{i=1}^{n}\sum_{k=1}^{n}\frac{1}{k}$ (3)
  $\displaystyle =$ $\displaystyle 2nH_n = O(n\lg n),$ (4)

where $ H_n$ is the $ n$th Harmonic number.

The worst case behavior is $ \Theta(n^2)$, but this almost never occurs (with high probability it does not occur) with random pivots.



"quicksort" is owned by thouis.
(view preamble)

View style:

See Also: sorting problem

Keywords:  comparison sort, quick-sort

Cross-references: harmonic number, necessary, expectation, summation, separated, pivot, recursive, tree, node, binary tree
There are 4 references to this entry.

This is version 10 of quicksort, born on 2003-10-07, modified 2006-08-06.
Object id is 4763, canonical name is Quicksort.
Accessed 7416 times total.

Classification:
AMS MSC68P10 (Computer science :: Theory of data :: Searching and sorting)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)