quicksort

Quicksort is a divide-and-conquer algorithm for sorting in thecomparison model. Its expected running time is $O(n\lg n)$ forsorting $n$ values.

Algorithm

Quicksort can be implemented recursively, as follows:

Algorithm Quicksort($\mathrm{L}$)
Input: A list $L$ of $n$ elements
Output: The list $L$ in sorted order
if $n>1$ then
         $p\leftarrow \text{ random element of }L$

$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 thecomputation as a binary tree. Each node of the tree corresponds toone recursive call to the quicksort procedure.

Consider the initial input to the algorithm, some list $L$. Call theSorted list $S,$ with $i$th and $j$th elements $S_i$ and $S_j.$ Thesetwo elements will be compared with some probability $p_{ij}$. Thisprobability 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 comparisonsonly occur against the pivot.

• No element between $S_i$ and $S_j$ can have already been chosenas a pivot before $S_i$ or $S_j$ is chosen. Otherwise, would beseparated into different sublists in the recursion.

The probability of any particular element being chosen as the pivot isuniform. Therefore, the chance that $S_i$ or $S_j$ is chosen as thepivot before any element between them is $2/(j-i+1)$. This isprecisely $p_{ij}.$

The expected number of comparisons is just the summation over allpossible comparisons of the probability of that particular comparisonoccurring. By linearity of expectation, no independence assumptionsare necessary. The expected number of comparisons is therefore

${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j>i}^n}{p}_{ij}$$=$${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j>i}^n}{\displaystyle \frac{2}{j-i+1}}$(1)

$=$${\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{k=2}^{n-i+1}}{\displaystyle \frac{2}{k}}$(2)

$\le$$2{\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{k=1}^n}{\displaystyle \frac{1}{k}}$(3)

$=$$2n{H}_n=O(n\lg n),$(4)

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

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