Suggest edit — quicksort

Title

Name

Note

---
title: "quicksort"
type: concept
related: [Quicksort, Randomized Algorithum, K Select]
source: https://www.jemoka.com/posts/kbhquicksort/
confidence: high
status: active
---

A randomized algorithm for sorting.
pick a pivot partition the array into bigger and less than the pivot (see k-select) recurse on L, R return concatenated L, pivot, R additional information stability quicksort is not stable (it doesn&rsquo;t preserve equal elements&rsquo; 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} &amp;\sum_{a=1}^{n-1} \sum_{b=a+1}^{n}\mathbb{E}\qty [ X_{a,b}] \\ =&amp;\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 \\ =&amp; \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 pick a pivot swap pivot with whatever the last element of the list is (i.e. such that the pivot is at the end) initialize two pointers \(a,b\) 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\).