## You are here

Homequicksort

## Primary tabs

# quicksort

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

$p\leftarrow\mbox{ random element of }L$

$A\leftarrow\{x|x\in L,x<p\}$

$B\leftarrow\{z|z\in L,z=p\}$

$C\leftarrow\{y|y\in L,y>p\}$

$S_{A}\leftarrow Quicksort(A)$

$S_{C}\leftarrow Quicksort(C)$

return $Concatenate(S_{A},B,S_{C})$

else

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:

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\leq$ | $\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.

## Mathematics Subject Classification

68P10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections