Introduction

The Quicksort algorithm depends on the distribution of the keys in the input vector. For what follow we assume to have a probability space $\Omega = D_n$, where $D_n$ is the set of permutation of length $n$ without repetition over $\{1,\ldots,n\}$. We focus on the simpler variant where the pivot is chosen as the right-most key. In the following table, we study the behavior of an application to the vector $\left ( 20, 25, 7, 3, 30, 8, 41, 18\right)$. $$ \begin{array}{cccccccccc} \hline 20 & 25 & 7 & 3 & 30 & 8 & 41 & 18 & & \\ \uparrow i & & & & & \uparrow j & & \uparrow pivot & \rightarrow & \{20, 41, 8\} \\ \hline 8 & 25 & 7 & 3 & 30 & 20 & 41 & 18 & & \\ & \uparrow i & & \uparrow j & & & & \uparrow pivot & \rightarrow & \{25, 30, 3\} \\ \hline 8 & 3 & 7 & 25 & 30 & 20 & 41 & 18 & & \\ & & \uparrow j & \uparrow i & & & & \uparrow pivot & \rightarrow & \{7, 25, 7\} \\ \hline 8 & 3 & 7 & 18 & 30 & 20 & 41 & 25 & & \\ & & & \uparrow pivot & & & & & \rightarrow & recursion \\ \hline \end{array} $$

Observe that in order to move the $pivot$ element in its final position, it is necessary for two keys ($7, 25$) to be checked twice against the $pivot$, moreover when the second of those checks happens, indexes $i$ and $j$ overlapped at some time such that $j < i$ eventually holds.

Hence, given a vector of length $n$, the number of checks performed before recurring on left and right partitions is $(n-1) + 2$, where $n-1$ appears because the $pivot$ element isn't indexed neither with $i$ nor with $j$. We analyze the number of performed checks by cases:

• worst case when the vector is already ordered, in either one of the two directions, recursion works over one partition only, because the other one has to be empty, hence the number of checks satisfies the following relation $ C(n) = (n-1)+2 + C(n-1) $. Unfolding $C(n-1)$ and fixing $C(0) = 0$ as base case, the following holds: $$ \begin{split} C(n) &= (n+1) + C(n-1) = (n+1) + n + C(n-2) = \\ &= (n+1) + n + (n-1) + \ldots + 2 + C(0) = \\ &= \sum_{k=2}^{n+1}{k} + C(0) = \sum_{k=1}^{n+1}{k} -1 + C(0) = \frac{(n+1)(n+2)}{2} - 1 \end{split} $$ so $C(n) \in O(n^2)$.
• best case when the partition phase puts the $pivot$ element in the middle then QUICKSORT recurs on balanced partitions. In this case it has the same complexity of MERGESORT, hence $C(n) \in O(n \log n)$

We explain the average case in the following dedicated section.

On number of checks, the average case

To study this case we have to consider all elements of $\Omega$ (recall that $w \in \Omega \rightarrow (w[i]\in \{1,\ldots,n\}) \wedge (\forall i\not =j: w[i]\not=w[j]) \wedge length(w) = n$). Let $j$ be the $pivot$ element, hence a generic $w$ will have this structure: $ w = (C_{j-1} \quad C_{n-j} \quad j)$, where $C_k$ is a vector of length $k$. Assume that the random variable $X =$ "$ j \in \lbrace 1,\ldots,n \rbrace \text{ is the $pivot$ element in } w$" is uniformly distributed, formally: $$ \mathbb{P}\left(w\in\Omega: w[n]=j \right) = \frac{(n-1)!}{n!} = \frac{1}{n} $$

Our goal here is to build a function $C(n)$ which counts the average number of checks during an execution of the algorithm given an input vector of length $n$. In order to do that observe that every key $j \in \{1,\ldots,n\}$ can be the $pivot$, so the following holds: $$ C(n) = (n+1) + \frac{1}{n}\sum_{j=1}^{n}{C(j-1) + C(n-j)} $$

Observing the sum when $j$ runs: $$ \begin{split} j=1 &\rightarrow C(0) + C(n-1) \\ j=2 &\rightarrow C(1) + C(n-2) \\ \ldots& \\ j=n-1 &\rightarrow C(n-2) + C(1) \\ j=n &\rightarrow C(n-1) + C(0) \\ \end{split} $$

Hence we can rewrite and manipulate: $$ \begin{split} C(n) &= (n+1) + \frac{2}{n}\sum_{j=0}^{n-1}{C(j)}\\ nC(n) &= n(n+1) + 2\sum_{j=0}^{n-1}{C(j)} \end{split} $$

Subtract the previous $(n-1)$ term to both members: $$ \begin{split} nC(n) -(n-1)C(n-1) &= n(n+1) + 2\sum_{j=0}^{n-1}{C(j)} -\left((n-1)((n-1)+1) + 2\sum_{j=0}^{(n-1)-1}{C(j)}\right) \\ % nC(n) -(n-1)C(n-1) &= n(n+1) + 2\sum_{j=0}^{n-1}{C(j)} -n(n-1) - 2\sum_{j=0}^{n-2}{C(j)} \\ &= n(n+1-(n-1)) + 2C(n-1) \\ &= 2(n + C(n-1)) \\ \end{split} $$

Getting $nC(n) = 2n + (n+1)C(n-1)$, divide both member by $n(n+1)$: $$ \begin{split} \frac{C(n)}{n+1} = \frac{2}{n+1} + \frac{C(n-1)}{n} \end{split} $$

Matching $A(n) = b(n) + A(n-1)$, where $A(n) = \frac{C(n)}{n+1} $ and $b(n) = \frac{2}{n+1} $. Unfolding $A(n-1)$ and fixing $C(0) = 0$: $$ \begin{split} \frac{C(n)}{n+1} &= \frac{2}{n+1} + \frac{C(n-1)}{n} = \frac{2}{n+1} + \frac{2}{n} + \frac{C(n-2)}{n-1}\\ &= \frac{2}{n+1} + \frac{2}{n} + \ldots + \frac{2}{3} + \frac{2}{2} + \frac{C(0)}{1}\\ &= \frac{2}{n+1} + \frac{2}{n} + \ldots + \frac{2}{3} + 1\\ &= 2\left(\frac{1}{n+1} + \frac{1}{n} + \ldots + \frac{1}{3}\right) + 1\\ &= 2\left(\frac{1}{n+1} + \frac{1}{n} + \ldots + \frac{1}{3}\right) +2\frac{1}{2} + 2 + 1 -2\frac{1}{2} - 2\\ &= 2\left(\frac{1}{n+1} + \frac{1}{n} + \ldots + \frac{1}{3} + \frac{1}{2} + 1\right) -2 \\ &= 2(H_{n+1}-1) \end{split} $$

where we recognized the $(n+1)$-th harmonic number $H_{n}=\left(\frac{1}{n+1} + \frac{1}{n} + \ldots + \frac{1}{3}+ \frac{1}{2}+ 1\right)$ to rewrite: $C(n) = 2(n+1)(H_{n+1}-1)$. Now recall the asymptotic approximation $H_n \sim ln(n) + \gamma$, so $C(n) \in O(n\log n)$.

From a practical point of view when a sorting problem is approached with the Quicksort algorithm, to avoid the worst case $O(n^2)$ number of checks, it is sufficient to do one of the following actions before starting the sorting process:

• shuffling the input vector and proceed with the algorithm described above;
• choose the $pivot$ element at random, move it in the right-most position and proceed with the algorithm described above.

Each one of these two tricks requires linear time in the dimension of the input vector and allows to work with $O(n\log n)$ number of checks, on average.

Symbolically

Unfolding

Define the recurrence relation as we did on paper, namely as an equation coupling an indexable symbol on both sides. Function make_recurrence_spec builds an object that denote the recurrence, formally and programmatically.

Function do_unfolding_steps allow us to perform unfolding or unrolling on occurrences of the inductively defined symbol. Doing $n$ steps of unfolding is the same to say to use the main recurrence defined above as a rewriting rule for occurrences, on the rhs, that pattern match with the one on the lhs.

Description and factorization

Playground

If desired, we can base the previous equation such that a new equation is produced containing the very first term of the sequence, in our case $c_{0}$.

Instantiation

Using the previous idea, finding a value for $n$ that causes the very first item to appear, then we can substitute in the entire specification.

If we attach a value to $c_{0}$ and we put it in the term cache, then it is possible to fully instantiate the spec.

Moreover, if we want to skip all little steps and perform a batch study for a variable number of steps, then we provide an higher-order operator ipython_latex, which produces a nice representation for a set of unfoldings

On the number of swaps, the average case

Our goal here is to build a function $S(n)$ which counts the average number of swaps during an execution of the algorithm given an input vector of length $n$.

The recurrence for the average number of swaps satisfies the following equation: $$ S(n) = \frac{n-2}{6} + \frac{1}{n} \sum_{j=1}^{n}{S(j-1) + S(n-j)} $$ We develop the proof in two stages, first studying equation (1): $$ \mathbb{E} \left[K_j \right] = \frac{(j-1)(n-j)}{n-1} $$ where $K_j$ is a random variable that depends on $j$, then equation (2): $$ \frac{n-2}{6} = \frac{1}{n}\sum_{j=1}^{n}{ \mathbb{E} \left[K_j \right] } $$ In what follow, assume to work over a probability space $\Omega$ as defined in the previous section, distributed uniformly.

Proof of equation (1)
Let $j \in \left \lbrace 1,\ldots,n \right\rbrace $ be the $pivot$ element, and let $K_j: \Omega \rightarrow \mathbb{R}$ be a random variable such that $K_j = s \mathbb{1}_{\lbrace w[n]=j \rbrace}$, where $s$ is the number of swaps performed by the partitioning phase given an input vector $w$ of length $n$. To better understand, $K_j$ satisfies the following implications: $$ \begin{split} w[n] = j &\rightarrow K_j(w) = s \\ w[n] \not= j &\rightarrow K_j(w) = 0 \\ \end{split} $$ The probability to have $k$ swaps when $j$ is the $pivot$ element is: $$ \mathbb{P}\left(K_j = k \right) = \frac{{{n-j}\choose{k}} {{j-1}\choose{k}} (n-j)! (j-1)! }{(n-1)!} $$ We can justify the above formula in the following steps:

• we have $k$ swaps when $\left| \left \lbrace w_i : w_i < j \right\rbrace \right| = k$ and $\left| \left \lbrace w_i : w_i > j \right\rbrace \right| = k$
• consider the set $\left \lbrace w_i : w_i < j \right\rbrace$: we can build permutations of length $j-1$, and foreach disposition we can choose $k$ keys in ${{j-1}\choose{k}}$ ways, hence the term ${{j-1}\choose{k}}(j-1)!$;
• consider the set $\left \lbrace w_i : w_i > j \right\rbrace$: we can build permutations of length $n-j$, and foreach disposition we can choose $k$ keys in ${{n-j}\choose{k}}$ ways, hence the term ${{n-j}\choose{k}}(n-j)!$;
• the total number of possible permutation of $n$ keys excluding the $pivot$ (which is fixed in the right-most position) is $(n-1)!$

Now we study the mean of the variable $K_j$: $$ \mathbb{E} \left[ K_j \right] = \sum_{k \geq 0}{k \mathbb{P}\left( K_j = k \right) } $$ Using ${{n}\choose{m}} = \frac{n!}{m!(n-m)!} $, we can rewrite: $$ \mathbb{P}\left(K_j = k \right) = {{n-j}\choose{k}} {{j-1}\choose{k}} \frac{(n-j)! (j-1)! }{(n-1)!} = {{n-j}\choose{k}} {{j-1}\choose{k}} {{n-1}\choose{j-1}}^{-1} $$ We put the previous rewrite of $\mathbb{P}\left(K_j = k \right)$ into the definition of $\mathbb{E} \left[ K_j \right]$: $$ \mathbb{E} \left[ K_j \right] = \sum_{k \geq 0}{k \mathbb{P}\left( K_j = k \right) } = \sum_{k \geq 0}{k \frac{{{n-j}\choose{k}} {{j-1}\choose{k}}}{{{n-1}\choose{j-1}}}} $$

Using the following rewrite for ${{j-1}\choose{k}}$: $$ {{j-1}\choose{k}} = \frac{(j-1)!}{k!(j-1-k)!} = \frac{(j-1)}{k} \frac{(j-2)!}{(k-1)!(j-1-k)!} = \frac{(j-1)}{k}{{j-2}\choose{k-1}} $$

and ${{n}\choose{m}} = {{n}\choose{n-m}}$ implies ${{j-2}\choose{k-1}} = {{j-2}\choose{j-2 -(k-1)}} = {{j-2}\choose{j -k-1}}$, then: $$ \begin{split} \mathbb{E} \left[ K_j \right] &= \sum_{k \geq 0}{k \mathbb{P}\left( K_j = k \right) } = \frac{1}{{{n-1}\choose{j-1}}} \sum_{k \geq 0}{k {{n-j}\choose{k}} {{j-1}\choose{k}}} \\ &= \frac{1}{{{n-1}\choose{j-1}}} \sum_{k \geq 0}{k {{n-j}\choose{k}} \frac{j-1}{k}{{j-2}\choose{j-k-1}}} = \frac{j-1}{{{n-1}\choose{j-1}}} \sum_{k \geq 0}{ {{n-j}\choose{k}} {{j-2}\choose{j-k-1}}} \end{split} $$

Now we recognize the Vandermonde result: $$ \sum_{k \geq 0}{{{r}\choose{k}} {{s}\choose{n-k}} } = {{r + s}\choose{n}} $$ which can be proved directly because the ipergeometric distribution has exactly the same structure, and being a distribution, it sum up to 1. So we use this result applying it to $\sum_{k \geq 0}{ {{n-j}\choose{k}} {{j-2}\choose{j-k-1}}} = {{n-2}\choose{j-1}} $, obtaining: $$ \begin{split} \mathbb{E} \left[ K_j \right] &= \frac{j-1}{{{n-1}\choose{j-1}}} {{n-2}\choose{j-1}} = \frac{(j-1)(n-2)!(j-1)!(n-j)!}{(n-1)!(j-1)!(n-j-1)!}=\\ &=\frac{(j-1)(n-2)!(j-1)!(n-j)(n-j-1)!} {(n-1)(n-2)!(j-1)!(n-j-1)!}= \frac{(j-1)(n-j)}{n-1} \end{split} $$ $\blacksquare$

Proof of equation (2)

Let us start with : $$ \begin{split} \frac{1}{n}\sum_{j=1}^{n}{\mathbb{E} \left[K_j \right] } &= \frac{1}{n} \sum_{j=1}^{n}{\frac{(j-1)(n-j)}{n-1}} = \frac{1}{n(n-1)} \sum_{j=1}^{n}{(j-1)(n-j)}=\\ &=\frac{1}{n(n-1)} \sum_{j=1}^{n}{(j(1+n)-j^2-n)} \\ &=\frac{1}{n(n-1)} \left( (n+1)\sum_{j=1}^{n}{j} - \sum_{j=1}^{n}{j^2} -n \sum_{j=1}^{n}{1} \right)\\ &=\frac{1}{n(n-1)}\left( \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6} - n^2 \right) = \frac{n-2}{6} \end{split} $$ as the following check confirm last simplification, by factoring the lhs:

$\blacksquare$

We are now ready to solve the main recurrence using the same strategy for the average number of checks, fixing $S(0) = S(1) = S(2) = 0$: $$ \begin{split} nS(n) - (n-1)S(n-1) &= \frac{2n-3}{6} + 2S(n-1)\\ \frac{S(n)}{n+1} &= \frac{S(n-1)}{n} + \frac{2n -3}{6n(n+1)} = % \frac{S(2)}{3} + \sum_{k=3}^{n}{ \frac{2k-3}{6k(k+1)} } \end{split} $$ Decomposing the general term of the summation $ \frac{2k-3}{6k(k+1)}$ in partial fractions yield: $$- \frac{1}{6 x - 6} + \frac{1}{2 x}$$ and integrating over $x$ yield: $$\frac{1}{2} \log{\left (x \right )} - \frac{1}{6} \log{\left (x - 1 \right )}$$ hence $S(n) \in O(n \log n)$.

Symbolically

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.