A randomized algorithm for sorting.

1. pick a pivot
2. partition the array into bigger and less than the pivot (see k-select)
3. recurse on L, R
4. return concatenated L, pivot, R

additional information

stability

quicksort is not stable (it doesn’t preserve equal elements’ order).

recurrence relationship

\begin{equation} T\qty(n) = T\qty(|L|) + T\qty(|R|) + O\qty(n) \end{equation}

recurse on left, recurse on right, the partitioning. In an idea world, suppose the array is split exactly in half, then:

\begin{equation} T\qty(n) = 2T\qty(\frac{n}{2}) O\qty(n) \end{equation}

which would be \(n \log \qty(n)\)

expected running time

Whether or not a pair of variables is compared is a random variable. Notice that a pair of values in quicksort is either compared once (because they were a pivot-value pair) or compared never (because they are in two arms of recursive calls).

Now, we can write:

\begin{equation} \mathbb{E}\qty [\sum_{a=1}^{n-1} \sum_{b=a+1}^{n} X_{a,b}] \end{equation}

where \(X_{a,b} \in \qty {0,1}\) is whether or not \(a,b\) is compared. By linearity of expectation:

\begin{align} &\sum_{a=1}^{n-1} \sum_{b=a+1}^{n}\mathbb{E}\qty [ X_{a,b}] \\ =&\sum_{a=1}^{n-1} \sum_{b=a+1}^{n} P\qty(X_{a,b} = 1) \cdot 1+ P\qty(X_{a,b} = 0) \cdot 0 \\ =& \sum_{a=1}^{n-1} \sum_{b=a+1}^{n} P\qty(X_{a,b} = 1) \end{align}

We have \(X_{a,b}=0\) if any value between them (i.e. \(\qty(a,b)\)) is chosen first as a pivot (i.e. such that \(a,b\) would then be separated into two parts).

And so, \(P\qty(X_{a,b}=1)\) is equivalently the probability of \(a\) or \(b\) being picked first out of \([a,b]\) for pivots (i.e. instead of numbers between them as pivots). The probability of this is \(P\qty(X_{a,b} = 1) = \frac{2}{b-a+1}\).

So, plunging this in, we will obtain:

\begin{equation} \mathbb{E}\qty [\sum_{a=1}^{n-1}\sum_{b=a+1}^{n} \frac{2}{b-a+1}] \leq 2n \log \qty(n) \end{equation}

worst-case running time

The worst case running time is choosing pivots that are always the maximum or minimum pivot, which just means that we keep merging, which is \(O\qty(n^{2})\).

doing it in place

1. pick a pivot
2. swap pivot with whatever the last element of the list is (i.e. such that the pivot is at the end)
3. initialize two pointers \(a,b\)
4. increment \(b\); when \(b\) sees something smaller than the pivot, swap \(a,b\) pointed values, and then increment \(a\) and \(b\)

Intutition: everything before \(a\) is smaller than the pivot; everything after \(a\) and before \(b\) is larger than the pivot, everything else is after \(b\).