| Version 3 |
Version 2 |
| \newcommand{\Lindent}{0.4in} |
\newcommand{\Lindent}{0.4in} |
| \newenvironment{Lalgorithm}[4]{ |
\newenvironment{Lalgorithm}[4]{ |
| \textbf{Algorithm} \textsc{#1}\texttt{(#2)}\newline |
\textbf{Algorithm} \textsc{#1}\texttt{(#2)}\newline |
| \textit{Input}: #3\newline |
\textit{Input}: #3\newline |
| \textit{Output}: #4\newline |
\textit{Output}: #4\newline |
| \newenvironment{Lfloatalgorithm}[6][h]{ |
\newenvironment{Lfloatalgorithm}[6][h]{ |
| \begin{figure}[#1] |
\begin{figure}[#1] |
| \caption{#2} |
\caption{#2} |
| \begin{Lalgorithm}{#3}{#4}{#5}{#6} |
\begin{Lalgorithm}{#3}{#4}{#5}{#6} |
| \end{Lalgorithm} |
\end{Lalgorithm} |
| \end{figure} |
\end{figure} |
| \newcommand{\Lgets}{\ensuremath{\gets}} |
\newcommand{\Lgets}{\ensuremath{\gets}} |
| \newcommand{\Lgroup}[1]{\textbf{begin}\\\hspace*{\Lindent}\parbox{\textwidth}{#1}\\\textbf{end}} |
\newcommand{\Lgroup}[1]{\textbf{begin}\\\hspace*{\Lindent}\parbox{\textwidth}{#1}\\\textbf{end}} |
| \newcommand{\Lif}[2]{\textbf{if} #1 \textbf{then}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
\newcommand{\Lif}[2]{\textbf{if} #1 \textbf{then}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
| \newcommand{\Lelse}[1]{\textbf{else}\\\hspace*{\Lindent}\parbox{\textwidth}{#1}} |
\newcommand{\Lelse}[1]{\textbf{else}\\\hspace*{\Lindent}\parbox{\textwidth}{#1}} |
| \newcommand{\Lelseif}[2]{\textbf{else if} #1 \textbf{then}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
\newcommand{\Lelseif}[2]{\textbf{else if} #1 \textbf{then}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
| \newcommand{\Lfor}[2]{\textbf{for} #1 \textbf{do}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
\newcommand{\Lfor}[2]{\textbf{for} #1 \textbf{do}\\\hspace*{\Lindent}\parbox{\textwidth}{#2}} |
| Quicksort is a divide-and-conquer algorithm for sorting in the |
Quicksort is a divide-and-conquer algorithm for sorting in the |
| comparison model. Its expected running time is $O(n\lg n)$ for |
comparison model. Its expected running time is $O(n\lg n)$ for |
| sorting $n$ values. |
sorting $n$ values. |
| \subsection*{Algorithm} |
|
| Quicksort can be implemented recursively, as follows: |
Quicksort can be implemented recursively, as follows: |
| \begin{Lalgorithm}{Quicksort}{$L$}{A list $L$ of $n$ elements}{The list $L$ in sorted order} |
\begin{Lalgorithm}{Quicksort}{$L$}{A list $L$ of $n$ elements}{The list $L$ in sorted order} |
|
\Lif{$n > 1$}{
|
\Lif{$n>1$}{
|
| $p \gets \mbox{ random element of } L$\\ |
$p \gets \mbox{ random element of } L$\\ |
| $A \gets \{x | x \in L, x < p\}$\\ |
$A \gets \{x | x \in L, x < p\}$\\ |
| $B \gets \{z | z \in L, z = p\}$\\ |
$B \gets \{z | z \in L, z = p\}$\\ |
| $C \gets \{y | y \in L, y > p\}$\\ |
$C \gets \{y | y \in L, y > p\}$\\ |
| $S_A \gets Quicksort(A)$\\ |
$S_A \gets Quicksort(A)$\\ |
| $S_C \gets Quicksort(C)$\\ |
$S_C \gets Quicksort(C)$\\ |
| {\bf return} $Concatenate(S_A,B,S_C)$\\ |
{\bf return} $Concatenate(S_A,B,S_C)$\\ |
| \Lelse{{\bf return} $L$} |
\Lelse{{\bf return} $L$} |
| \end{Lalgorithm} |
\end{Lalgorithm} |
| Its worst case running time is $\Theta(n^2)$, but this almost never |
Its worst case running time is $\Theta(n^2)$, but this almost never |
| occurs using random |
occurs using random pivots. |
| \subsection*{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: |
|
| \begin{itemize} |
|
| \item $S_i$ or $S_j$ must be chosen as a pivot $p$, since comparisons |
|
| only occur against the pivot. |
|
| \item 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. |
|
| \end{itemize} |
|
| 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 |
|
| occuring. By linearity of expectation, no independence assumptions |
|
| are necessary. The expected number of comparisons is therefore |
|
| \begin{eqnarray} |
|
| \sum_{i=1}^{n}\sum_{j>i}^{n}p_{ij} & = & \sum_{i=1}^{n}\sum_{j>i}^{n}\frac{2}{j-i-1} \\ |
|
| & = & \sum_{i=1}^{n}\sum_{k=2}^{n-i+1}\frac{2}{k}\\ |
|
| & \le & 2\sum_{i=1}^{n}\sum_{k=1}{n}\frac{1}{k}\\ |
|
| & = & 2nH_n = O(n\lg n), |
|
| \end{eqnarray} |
|
| where $H_n$ is the $n$th Harmonic number. |
|
