# Quick Sort

## Algorithm

```proc quick-sort(A, p, r) if p < r then q = partition(A, p, r) quick-sort(A, p, q-1) quick-sort(A, q+1, r)``````func partition(A, p, r) x = A[r] i = p-1`````` for j = p to r-1 do if A[j] < r then i = i + 1 A[i] <-> A[j] A[i+1] <-> A[r] return i+1```

## Comparisons

For the worst case, the list is already sorted.

• $T\left(n\right)=\left(n-1\right)+T\left(n-1\right)$
• $=\underset{i=1}{\overset{n-1}{\Sigma }}i$
• $=\frac{\left(n-1\right)n}{2}$

For the best case, partitions are equally sized.

• $T\left(n\right)=2T\left(\frac{n-1}{2}\right)+\left(n-1\right)$
• $\le 2T\left(\frac{n}{2}\right)+\left(n-1\right)$
• $\approx nlgn-n+1$ (constructive induction)

For the average case, we can approximate with a reccurence:

• $T\left(n\right)=T\left(3\frac{n}{4}\right)+T\left(\frac{n}{4}\right)+\left(n-1\right)$
• $\approx 1.23nlgn$

The exact reccurence is:

$T\left(n\right)=\left\{\begin{array}{cc}0& ifn=1\\ \left(n-1\right)+\underset{q=1}{\overset{n}{\Sigma }}\left(\frac{1}{n}\right)\left(T\left(q-1\right)+T\left(n-q\right)\right)& \text{otherwise}\end{array}$

The closed form solution (through constructive induction) is: $\approx 1.39nlgn$.

Another more clever argument can be used to get the exact answer without the difficult reccurence. Consider elements $i$ and $j$ such that $i. Consider choice of pivot $k$:

1. If $k this has no effect.
2. If $k=i$ the elements are compared.
3. If $i the elements aren’t compared.
4. If $k=j$ the elements are compared.
5. If $j this has no effect.

We just sum the probability that each pair is compared to one another:

• $\underset{1\le i\le j\le n}{\Sigma }\frac{2}{j-i+1}$
• $=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=i+1}{\overset{n}{\Sigma }}\frac{2}{j-i+1}$
• $=2\left(n+1\right){H}_{n}+4n$