\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Analysis of Quicksort (6)}
\author{Michael L. Littman}
\date{September 15th, 1998}

\maketitle 

\section{PROBLEM WITH QUICKSORT}

\subsection{Review}

\ni Last time, we talked about several algorithms for sorting.

\ul

\li Insertion sort, bubble sort, and selection sort are all
$\Theta(n^2)$ algorithms in the worst case.

\li Merge sort is $\Theta(n \log n)$ in the worst case.

\li Quicksort is a lot like merge sort on average...

\el


\subsection{Quicksort Algorithm}

\ni Start with an array $A$ with elements $0$ to $n-1$.

\ni Call {\tt quicksort( data, 0, data.size() - 1 )} to sort all
elements from $0$ to $n-1$. 
 

\begin{verbatim}
void quicksort( vector<int> & data, int start, int end )
{
  if( start < end )
  {   
    int boundary = partition( data, start, end, start );
    quicksort( data, start, boundary-1 );
    quicksort( data, boundary + 1, end );
  }
}
\end{verbatim}


\subsection{Partition}

\ni Here, {\tt partition(data,i,j,l)} partitions array elements $A[i]$
through $A[j]$ around $A[l]$.  It returns $k$, the index where the
partition element ends up.

\ni $\begin{array}{ccccccc}
i&\ldots& k-1& k& k+1& \ldots& j
\end{array}$

\ni After partitioning, element $k$ is in its correct, sorted place,
all the elements from $i$ to $k-1$ are less than $A[k]$, and all the
elements from $k+1$ to $j$ are greater than $A[k]$ (and transitively,
elements $i$ through $k-1$).


% choose k randomly between i and j

\subsection{Analysis}

\ni The running time depends a lot on where $k$ ends up.  We call this
the {\em split\/}.

\ni If $k$ is equal to $i$ or $j$ every time, we get
\ul
\li $T(n) = n + T(n-1)$; $T(n) = \Theta(n^2)$.
\el

\ni This is a {\em very bad\/} split.

\ni If $k$ is halfway between $i$ and $j$, we get
\ul
\li $T(n) = n + 2 T(n/2)$; $T(n) = \Theta(n \log n)$.
\el

\ni This is a {\em very good\/} split.

\ni In fact, it is possible to show that the running time is $O(n^2)$
 and $\Omega(n\log n)$; these are the worst and best cases,
 respectively.

\subsection{Expected Case?}

\ni This analysis doesn't really tell us what to expect.  In practice,
quicksort behaves like a fast $n \log n$ algorithm, but our focus on
worst-case running time tells us it's $n^2$.

\ni What gives?

\ni The fact of the matter is, we can always force this version of
quicksort to take quadratic time by a careful choice of input.  Like?

\ni In general, any deterministic scheme for picking the pivot is
susceptible to being manipulated into consistently bad splits.

\subsection{Rock, Paper, Scissors}

\ni This is actually a fairly general phenomenon.

\ni {\bf Rock, Paper, Scissors:}

\ul

\li[1.] rock smashes scissors,
\li[2.] scissors cut paper,
\li[3.] paper covers rock.

\el

\ni Strategies:
\ul
\li Always rock.
\li Alternate rock-paper-scissors.
\li First rock, then whatever opponent chose last time.
\el

\subsection{Importance of Being Random}

\ni If I ``publish'' my deterministic strategy, you crush me.

\ni What if I use a randomized strategy?  Even if I tell you what it
is, you don't get any leverage over me.

\ni Expected tie game, regardless of your strategy.

\ni Best case: win; worst case: loss; average over many games: draw.

\subsection{Preview}

\ni We can use this insight to adapt quicksort so that it has the same
sort of behavior.

\ni We will pick our pivot {\em randomly\/}.

\ni Sometimes this will lead to a bad split, and sometimes to a good
split, but no one can {\em force\/} a bad split.

\ni This will lead to an algorithm with expected running time of
$\Theta(n \log n)$.


\section{PROBABILITY THEORY}

\subsection{Probability}

\ni To formalize this sort of argument, we're going to appeal to
probability theory.

\ni Intuitively, we say an event has probability $p$, if, given
identitical circumstances, the event occurs $1000p$ out of $1000$
times.

\ni For example, if there is a 1\% chance of thunderstorms today, then
only one day like this out of 100 ends up with thunderstorms.


\subsection{Language of Probability}

\ni Basic concepts:

\ul

\li We assign probabilities to outcomes of {\em experiments\/}.

\li A possible outcome $e$ is called an {\em elemental event\/}.

\li The set $S$ of all elemental events is called the {\em sample
space\/}.

\li The elemental events are {\em mutually exclusive\/} and {\em
exhaustive\/}, that is, they {\em partition\/} the sample space.

\li A set $A$ of  elemental events is an {\em event\/}.

\el

\ni Concrete example: coin flip.

\subsection{Axioms of Probability}

\ni Axioms:

\ul

\li[1.] $\Pr\{A\} \ge 0$ for any event $A$.

\li[2.] $\Pr\{S\} = 1$.

\li[3.] $\Pr\{A \cup B\} = \Pr\{A\}+\Pr\{B\}$ for disjoint events $A$
and $B$.

\el


\subsection{Probability Properties}

\ni From the axioms, we can conclude:

\ul

\li $0 \le \Pr\{A\}\le 1$ for all events $A$.

\li $\Pr\{A\} = \sum_{e\in A} \Pr\{e\}$

\el

\ni Additional terms:

\ul

\li $\Pr\{A\}$ is the {\em probability\/} of event $A$.

\li An assignment of probabilities to all elemental events is a {\em
discrete probability distribution\/}.

\li The discrete probability distribution $\Pr\{e\} = 1/|S|$ for all
$e\in S$ is called the {\em uniform distribution\/}.

\el

\subsection{Counting}

\ni Often, to assign probabilities to events, we need to know how many
events there are.

\ni Some standard examples:

\ul

\li Number of binary numbers with 10 bits: $2^{10} = 1024$.
\li Number of possible four letter words starting with a vowel: $5
\cdot 26^3 = 87880$.
\li Number of permutations of ``algorithm'': $9! = 362880$.
\li Number of distinct permutations of ``abba'':
$\left(\begin{array}{c}4\\2\end{array}\right) = \frac{4!}{2! 2!} = 6$.

\el

\subsection{Combinatorial Sample Spaces}

\ni We can build complex sample spaces out of simpler ones.

\ul

\li Let sample space $S_1$ be the outcomes of a single coin-flip
experiment: $S_1 = \{ \mbox{heads}, \mbox{tails} \}$, with
$\Pr\{\mbox{heads}\} = \Pr\{\mbox{tails}\} = 1/2$ (uniform
distribution).

\li Let $S_2$ be the outcomes of an ordered pair of coin-flip
experiments: $S_2 = S_1 \times S_1 = \{ \mbox{heads heads},
\mbox{heads tails}, \mbox{tails heads}, \mbox{tails tails} \}$.

\li Assuming {\em independent and identically distributed\/} (i.i.d.)
trials, we can infer, e.g., that $\Pr\{\mbox{tails heads}\} =
\Pr\{\mbox{tails}\} \Pr\{\mbox{heads}\} = 1/4$.  The resulting
distribution is again uniform.

\el

\ni Similarly, we can define a uniform distribution over the sample
space of permutations out of a smaller number of simpler sample
spaces.

% shuffle?


\subsection{Coin-flip Experiment}

\ni What's the probability that we pick a number near the middle (2-5)?

\ni Coin flip to numbers:
\ul
\li TTT 0
\li TTH 1
\li THT 2
\li THH 3
\li HTT 4
\li HTH 5
\li HHT 6
\li HHH 7
\el

\ni Estimated probability is success divided by attempts.

% 62.5 / 100

\subsection{Expectation}

\ni Sometimes we associate a numerical value with each elemental event
and want to know the {\em average\/} or {\em expected\/} value.

\ni Let $f: S \rightarrow \Re$.  The expected value of $f$ is $E[f] =
\sum_{e \in S} \Pr\{e\} f(e)$.

% 3.5

\ni For example, what's the expected coin flip value from the previous
experiment?

\ni Note that this is not saying that one value is more likely than
the others.  It is identifying the average value we get if we repeat
the experiment.

\subsection{Expected Running Time}

\ni We can use the notion of expectations to characterize the running
time of a randomized algorithm.

\ni The expected running time is $\sum_t t \Pr\{t\}$, where $t$ is a
possible running time for the algorithm and $\Pr\{t\}$ is the
probability that this running time occurs.

\subsection{Example}

\ni Note that there are cases in which the expected running time of an
algorithm is very fast, but there is {\em no\/} bound on the
worst-case running time.

\begin{algorithm}{HaveGirl}{}
 \begin{REPEAT} 
   \mbox{\it kid} \= \mbox{\sc RandBaby}()
 \end{REPEAT}{\mbox{\sc sex}(\mbox{\em kid}) = \mbox{\em female}}\\
 \RETURN
\end{algorithm}

\ul
\li $T = 1 + 1/2\; (0) + 1/2\; T$
\li $T = 1 + 1/2 + 1/4 + 1/8 + ...$
\li $T = 2$
\el 

\section{RANDOMIZED QUICKSORT}

\subsection{Basic Idea}

\ni To avoid getting slammed with a worst-case input, we're going to
pick our pivots randomly from the set of possible pivots.

\ni Caveat: Our analysis will assume that elements in the list are
distinct so there are no tie-breaking issues on the final position of
the pivot.  If we define the algorithm properly, duplicate elements in
the list only help, so we ignore this case here.


\subsection{Code}

\begin{verbatim}
void quicksort( vector<int> & data, int start, int end, RandGen & rand )
{
  if( start < end )
  {   
    int boundary = partition( data, start, end,
			      rand.RandInt( start, end ) );
    quicksort( data, start, boundary, rand );
    quicksort( data, boundary + 1, end, rand );
  }
}

void quicksort( vector<int> & data )
{
  RandGen rand;
  quicksort( data, 0, data.size() - 1, rand ); 
}     
\end{verbatim}



% \subsection{Caveat}

%  this analysis assumes entries are distinct.  Otherwise, we need to
% say what {\sc partition} returns when more than one element is equal
% to the pivot.

\subsection{Expected-Case Recurrence}

\ni Because we select the pivot at random, we are equally likely to
get each possible split.

\ni We can express the expected running time as:

\ul

\li $T(0) = 0$
\li $T(n) = \sum_{k = 0}^{n-1} \frac{1}{n} [n+T(k) + T(n-k-1)]$
\li $= n+ \frac{1}{n} \sum_{k = 0}^{n-1} [T(k) + T(n-k-1)]$

\el

\ni $k$ is the number of ``lows.''


\subsection{Good and Bad Splits}

\ni To simplify our analysis of this recurrence, we will artificially
divide the world into two categories.

\ul

\li A {\em good split\/} is one in which $i+1/4\;(j-i+1) \le k \le
j-1/4\;(j-i+1)$ .
\li A {\em bad split\/} is one in which $i \le k < i+1/4\;(j-i+1)$ or
$j-1/4\;(j-i+1)< k \le j$ .

\el

\ni The probability of a good split is $1/2$ and the probability of a
bad split is $1/2$.



\subsection{Expected Run Time}

\ni We get a mix of good and according to their relative
probabilities.

\begin{eqnarray*}
% \htmlimage{}
T(n) &=& n + {1/n}\; \sum_{k = 0}^{n-1} [T(k) + T(n-k-1)]\\
&=& n + \frac{2}{n}\sum_{k = n/2}^{n-1} [T(k) + T(n-k-1)]\\
&=& n + \frac{2}{n}\sum_{k = n/2}^{3n/4} [T(k) + T(n-k-1)] + \frac{2}{n}\sum_{k = 3n/4}^{n-1} [T(k) + T(n-k-1)]\\
&\le& n + \frac{2}{n}\sum_{k = n/2}^{3n/4} [T(3n/4) + T(n/4)] + \frac{2}{n}\sum_{k = 3n/4}^{n-1} [T(n-1) + T(0)]\\
&\le& n + \frac{2}{n} (n/4) [T(3n/4) + T(n/4)]  + \frac{2}{n} (n/4) T(n-1)\\
&\le& n + 1/2\; [T(3n/4) + T(n/4)] + 1/2\; T(n-1)
\end{eqnarray*}


\subsection{Asymptotic Bound}

\ni Now, we want to show that $T(n) \le c n \log n$ for some constant $c$.
\ul
\li True for small $n$.
\li Assume true for $n' < n$.
\el
\begin{eqnarray*}
% \htmlimage{}
T(n) &\le& n + 1/2\; [T(3n/4) + T(n/4)] + 1/2\; T(n-1)\\
&\le& n + 1/2\; [c (3n/4)\log(3n/4) + c (n/4)\log(n/4)]+ 1/2\; c (n-1)\log(n-1)\\
&\le& n + c (3n/8)\log(n)- c(3n/8)\log(4/3) + c (n/8)\log(n)-c (n/8)\log(4) + c n/2 \log(n)\\
&=& n + c (8n/8)\log(n) - c(3n/8)(2-\log(3)) -c (n/4)\\
&=&  c n \log(n) + n (1 - c(3/8)(2-\log(3)) -c/4)\\
&\le& c n \log n, \mbox{if $c \ge 3$}
\end{eqnarray*}

\ni So, $T(n) = O(n\log n)$

\subsection{Wrap Up}

\ni Probability of getting lots of bad splits is very small.  With
high probability we divide the list into fractional pieces (instead of
just nibbling off a constant-size piece).  This is enough balance to
get asymptotic $n\log n$ running time.

\ni We could also prove an $n \log n$ lower bound on the expected
running time (but we won't).

\end{document}
