> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-ii-sorting-and-order-statistics/7.-quicksort.md).

# 7. Quicksort

## Exercises

### 7.1-1

Coloring is similar as in the book, whilst indexing is the same.

13  19  9  5  12  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:blue;">13</mark>  19  9  5  12  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:blue;">13  19</mark>  9  5  12  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9</mark>  <mark style="background-color:blue;">19  13</mark>  5  12  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5</mark>  <mark style="background-color:blue;">13  19</mark>  12  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5</mark>  <mark style="background-color:blue;">13  19  12</mark>  8  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8</mark>  <mark style="background-color:blue;">19  12  13</mark>  7  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7</mark>  <mark style="background-color:blue;">12  13  19</mark>  4  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7  4</mark>  <mark style="background-color:blue;">13  19  12</mark>  21  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7  4</mark>  <mark style="background-color:blue;">13  19  12  21</mark>  2  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7  4  2</mark>  <mark style="background-color:blue;">19  12  21  13</mark>  6  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7  4  2  6</mark>  <mark style="background-color:blue;">12  21  13  19</mark>  <mark style="background-color:yellow;">11</mark>\ <mark style="background-color:red;">9  5  8  7  4  2  6</mark>  <mark style="background-color:yellow;">11</mark>  <mark style="background-color:blue;">21  13  19  12</mark>

### 7.1-2

**Available in the latest revision of the IM.**

### 7.1-3

**Available in the latest revision of the IM.**

### 7.1-4

**Available in the latest revision of the IM.**

### 7.2-1

**Available in the latest revision of the IM.**

### 7.2-2

**Available in the latest revision of the IM.**

{% hint style="info" %}
If we use a partitioning scheme introduced in [Exercise 7.1-2](#id-7.1-2), then the running time is $$\Theta(n \lg n)$$.
{% endhint %}

### 7.2-3

**Available in the latest revision of the IM.**

### 7.2-4

**Available in the latest revision of the IM.**

{% hint style="warning" %}
Nearly sorted input will push QuickSort toward the worst-case scenario, rather than the best-case, as hinted in the IM.
{% endhint %}

### 7.2-5

**Available in the latest revision of the IM.**

### 7.2-6

**Available in the latest revision of the IM.**

### 7.3-1

**Available in the latest revision of the IM.**

### 7.3-2

**Available in the latest revision of the IM.**

### 7.4-1

We guess that $$T(n) \ge cn^2$$ for some constant $$c >0$$. Substituting this guess into recurrence (7.1) yields

$$
\begin{align\*}
T(n)&\ge\max{cq^2+c(n-1-q)^2:0\le q\le n-1}+\Theta(n) \\
&=c\max{q^2+(n-1-q)^2:0\le q\le n-1}+\Theta(n) \\
&= c(n-1)^2+\Theta(n) && \text{(when $q=0 \lor q=n-1$)} \\
&=cn^2-c(2n-1)+\Theta(n) \\
&\ge cn^2
\end{align\*}
$$

by picking the constant $$c$$ small enough that the $$\Theta(n)$$ term dominates. Therefore, $$T(n)=\Omega(n^2)$$.

### 7.4-2

**Available in the latest revision of the IM.**

### 7.4-3

$$
q^2+(n-1-q)^2=(n-1)^2+2q(q-(n-1)).
$$

$$0 \le q \le n-1$$ implies that $$2q(q-(n-1)) \le 0$$. When this expression is zero, we have a maximum. It is a quadratic polynomial having at most two distinct roots, so $$q= 0 \lor q=n-1$$.&#x20;

### 7.4-4

$$
\begin{align\*}
\mathbb{E}{\[X]} &= \sum\_{i=1}^{n-1} \sum\_{j=i+1}^n \frac{2}{j-i+1} \\
&= \sum\_{i=1}^{n-1} \sum\_{k=1}^{n-i} \frac{2}{k+1} \\
&= 2\sum\_{i=1}^{n-1} \left(\sum\_{k=1}^{n-i+1} \frac{1}{k}-1\right) \\
&\ge 2\sum\_{i=1}^{n-1} \left(\ln {(n-i+2)} -1\right) && \text{(by equation (A.20))} \\
&= 2\left(\sum\_{i=3}^{n+1} \ln i - (n-1)\right) \\
&= 2 \left(\ln \prod\_{i=3}^{n+1} i-(n-1)\right) \\
&\ge 2\ln \prod\_{i=1}^n i-2n && \text{(for sufficiently large $n$)}  \\
&= 2\ln n! -2n \\
&= \Theta(n\lg n) && \text{(by equation (3.28))}.
\end{align\*}
$$

This bound and Lemma 7.1 allow us to conclude that the expected running time of `Randomized-Quicksort` is $$\Omega(n\lg n)$$.

### 7.4-5

Insertion sort requires $$O(k^2)$$ time to sort an array of size $$k$$. The total time spent by insertion sort is $$O(n/k) \cdot O(k^2)=O(nk)$$, since we can have at most $$n/k$$ subarrays of size $$k$$. The expected number of levels in the recursion tree is $$O(\lg (n/k))$$. Therefore, the total time spent in partitioning subarrays is $$O(n\lg(n/k))$$. After summing up these terms, we get that the randomized version of this sorting algorithm runs in $$O(nk+n\lg (n/k))$$ expected time.

The modified algorithm has the same asymptotic running time as standard randomized quick-sort when $$O(nk+n\lg (n/k))=O(n\lg n)$$. The largest asymptotic value of $$k$$, as a function of $$n$$, that satisfies this condition is $$k=\Theta(\lg n)$$. Notice that $$k$$ cannot be asymptotically larger than $$\Theta(\lg n)$$, otherwise $$nk=\omega(n\lg n)$$ and we would make things worse. On the other hand, plugging in $$k=\lg n$$ into our formula for the expected running time gives

$$
O(n\lg n+n\lg (n/\lg n))=O(2n\lg n-n\lg \lg n)=O(n\lg n).
$$

In practice, you would need to experimentally find the best $$k$$, as performance depends on many other machine related factors.

{% hint style="info" %}
There is a fun practical trick, where you don't sort the small subarrays during the recursion at all. Instead, just let the quicksort recursion return doing absolutely nothing when size $$< k$$. You end up with one giant, nearly-sorted array where no element is more than $$k$$ positions away from its final sorted spot (see also [Exercise 7.2-4](#id-7.2-4)). Then, you run one single, massive insertion sort over the entire array at the very end. Because insertion sort runs in $$O(n + \text{inversions})$$ time, and the array is almost perfectly sorted, this single pass runs in exactly $$O(nk)$$ time, but it completely eliminates the overhead of calling the insertion sort function $$n/k$$ separate times!
{% endhint %}

### ★ 7.4-6

If the median falls into the lowest or largest $$\alpha n$$ numbers, then we get a worse than $$\alpha$$-to-$$(1-\alpha)$$ split. This happens if at least two randomly selected numbers belong in these ranges. We have the following 4 disjoint events:

1. All three numbers are among the lowest $$\alpha n$$ values.
2. All three numbers are among the largest $$\alpha n$$ values.
3. Exactly two numbers are among the lowest $$\alpha n$$ values.
4. Exactly two numbers are among the largest $$\alpha n$$ values.

Therefore, the total probability is

$$
p=\alpha^3+\alpha^3+\binom{3}{2}\alpha^2(1-\alpha)+\binom{3}{2}\alpha^2(1-\alpha)=2\alpha^2(3-2\alpha).
$$

## Problems

### 7-1 Hoare partition correctness

#### a.

Initialization:\
A=(13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21)\
p=1\
r=12\
x=13\
i=0\
j=13

After Iteration 1:\
A=(6, 19, 9, 5, 12, 8, 7, 4, 11, 2, 13, 21)\
i=1\
j=11

After Iteration 2:\
A=(6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21)\
i=2\
j=10

After Iteration 3:\
A=(6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21)\
i=10\
j=9\
RETURN 9

#### b.

`Hoare-Partition` produces a balanced split instead of hitting the worst-case scenario, as is the case with `Partition`. It better distributes repeated elements equal to pivot, so it works well even in presence of duplicates.

{% hint style="danger" %}
Nonetheless, `Hoare-Partition` is also terribly flawed by moving the pivot during the partitioning stage. This phenomenon is described [here](https://evarga.gitbook.io/sh-aofa/introduction/chapter-1-analysis-of-algorithms#exercise-1.13).
{% endhint %}

#### c.

We focus on the first iteration and show what happens to indices $$i$$ and $$j$$ as well as what transformation of $$A$$ ensures that none of these indices ever fall out of range. Initially, before entering the `while` loop, we have $$x=A\[p]$$, $$i=p-1$$ and $$j=r+1$$. The body of the loop runs as follows:

1. Index $$j$$ is decremented before reading $$A$$, so $$p \le j \le r$$ on first access.
2. It will be decremented until stumbling across an element not greater than $$x$$. Notice that $$j$$ cannot pass $$p$$, since $$x=A\[p]$$, hence we know that $$p\le j$$ after line 7.
3. Index $$i$$ is incremented before reading $$A$$, so $$p \le i\le r$$ on first access.
4. It will be incremented until stumbling across an element not smaller than $$x$$. Notice that $$i$$ cannot pass $$p$$, since $$x=A\[p]$$, hence we know that $$i=p$$ after line 10.

At this point, we have two possibilities at line 11:

1. If $$i=j$$, then the function returns $$p$$. This occurs when all other elements are greater than $$x$$.
2. Otherwise, we must have $$i\<j$$, so $$A\[i]$$ and $$A\[j]$$ are swapped. But exactly these values, now on opposite positions relative to indices $$i$$ and $$j$$, guard $$i$$ and $$j$$ from passing them. Furthermore, if either $$i$$ or $$j$$ (or both) stop at these locations, then we would surely have $$i > j$$ and the function would return $$j$$.

#### d.

Again, we focus our attention on the first iteration. From part (c) we know that $$p \le j$$ at termination. Before accessing $$A$$ index $$j$$ is decremented, so $$j \le r$$. Now, based on the fact that $$p\<r$$, we have two scenarios:

1. If $$A\[p] \ge A\[r]$$, then these values are exchanged, since at line 11 $$i=p$$ and $$j=r$$. In the next iteration, $$j$$ will be decremented at least once.
2. Otherwise, $$j$$ is immediately decremented below $$r$$.

At any rate, at termination we have that $$p \le j < r$$.

#### e.

Let's prove the next invariant:

*At the beginning of the `while` loop at lines 4-13,* $$i\<j$$*, the subarray* $$A\[p:i]$$ *contains elements less than or equal to the pivot, and the subarray* $$A\[j:r]$$ *contains elements greater than or equal to the pivot.*

**Initialization**\
Before entering the loop for the first time, we have $$x=A\[p]$$, $$i=p-1$$ and $$j=r+1$$. The empty subarrays $$A\[p:i]$$ and $$A\[j:r]$$ satisfy the invariant and $$i\<j$$.

**Maintenance**\
The `repeat-until` loop at lines 5-7 decreases $$j$$ up to some position $$j'\<j$$. We know that every element of $$A\[j'+1:j]$$ is greater than or equal to $$x$$. So, $$A\[j'+1:j] \cup A\[j:r]=A\[j'+1:r]$$ has only elements greater than or equal to $$x$$.

The `repeat-until` loop at lines 8-10 increases $$i$$ up to some position $$i'>i$$. We know that every element of $$A\[i:i'-1]$$ is less than or equal to $$x$$. So, $$A\[p:i] \cup A\[i:i'-1] =A\[p:i'-1]$$ has only elements less than or equal to $$x$$.

Let $$i=i'$$ and $$j=j'$$. After line 10, but before entering line 11, we have that the subarray $$A\[p:i-1]$$ contains elements less than or equal to the pivot, and the subarray $$A\[j+1:r]$$ contains elements greater than or equal to the pivot. Furthermore, $$A\[i] \ge x$$ and $$A\[j] \le x$$.

If $$i\<j$$ at line 11, then $$A\[i]$$ and $$A\[j]$$ are exchanged, so that the subarray $$A\[p:i]$$ contains elements less than or equal to the pivot and the subarray $$A\[j:r]$$ contains elements greater than or equal to the pivot. Hence, the invariant is reestablished for the next iteration.

**Termination**\
The `while` loop must eventually terminate, since both indices are moving closer to each other at every iteration. This happens when $$i\ge j$$ at line 11. Nonetheless, no elements are exchanged, so the postcondition stated in the previous section remains true. We can differentiate the following cases:

1. If $$i=j$$, then $$A\[i]=A\[j]$$, thus the subarray $$A\[p:j]$$ contains elements less than or equal to the pivot and the subarray $$A\[j+1:r]$$ contains elements greater than or equal to the pivot.
2. Otherwise, $$i>j \implies i-1 \ge j$$. Because $$i-1 \ge j$$, the segment $$A\[p : j]$$ is a subset of $$A\[p : i-1]$$. Since we already know that all elements in $$A\[p : i-1]$$ are $$\le x$$, it is guaranteed that all elements in $$A\[p : j]$$ are $$\le x$$. We also already established that $$A\[j+1 : r] \ge x$$.

In both cases, It is true the every element from $$A\[p:j]$$ is less than or equal to every element from $$A\[j+1:r]$$.

#### f.

```
Quicksort(A, p, r)
    if p < r
        q = Hoare-Partition(A, p, r)
        Quicksort(A, p, q)
        Quicksort(A, q + 1, r)
```

### 7-2 Quicksort with equal element values

**Available in the latest revision of the IM.**

{% hint style="warning" %}
There is an omission in the IM in part (c). `Randomized-Partition'` also differs at line 2, where $$A\[i]$$ must be exchanged with $$A\[p]$$ instead of $$A\[r]$$.
{% endhint %}

{% hint style="warning" %}
In part (d) the IM does not cover the best-case scenario. Namely, when all element values are equal, then `Quicksort'` runs in linear time.
{% endhint %}

### 7-3 Alternative quicksort analysis

**Available in the latest revision of the IM.**

### 7-4 Stooge sort

**Available in the latest revision of the IM.**

### 7-5 Stack depth for quicksort

**Available in the latest revision of the IM.**

### 7-6 Median-of-3 partition

#### a.

The three randomly selected elements must include $$z\_i$$ itself, one smaller than $$z\_i$$, and one larger than $$z\_i$$. These elements can be chosen in any order, so we should count the number of 3-sets satisfying these constraints among $$\binom{n}{3}$$ such sets. We have $$p\_i=\cfrac{6(i-1)(n-i)}{n(n-1)(n-2)}$$.

#### b.

We need to find $$\cfrac{p\_{\lfloor(n+1)/2 \rfloor}}{1/n}$$ at the limit, when $$n \to \infin$$. Observe that $$i=\lfloor(n+1)/2 \rfloor$$ tends to $$n/2$$ as $$n$$ increases. Therefore,

$$
\lim\_{n\to. \infin} \cfrac{\cfrac{6(n/2-1)(n-n/2)}{n(n-1)(n-2)}}{1/n}=\lim\_{n\to. \infin}  \cfrac{\cfrac{3}{2}(n^2-2n)}{n^2-3n+2}=\cfrac{3}{2}.
$$

#### c.

We need to find $$\lim\_{n \to \infin}\cfrac{\sum\_{i=n/3}^{2n/3} p\_i}{1/3}$$. Following the hint from the book, we approximate the sum by an integral, thus

$$
\begin{align\*}
\sum\_{i=n/3}^{2n/3} p\_i &\approx \int\_{n/3}^{2n/3} \frac{6(-x^2+nx+x-n)}{n(n-1)(n-2)}dx \\
&= \frac{6(-7n^3/81+3n^3/18+\Theta(n^2))}{n(n-1)(n-2)} \\
&\to \frac{13}{27} && \text{(when $n \to \infin$)}.
\end{align\*}
$$

Thus, the median-of-3 method increases the likelihood of getting a good split (compared with the ordinary implementation) by 13/9.

#### d.

According to [Exercise 7.4-2](#id-7.4-2), quicksort's best case running time is $$\Omega(n \lg n)$$. Thus, any technique that improves the chances of having good splits cannot influence its asymptotic lower bound.

### 7-7 Fuzzy sorting of intervals

#### a.

The `Fuzzy-Partition` function is similar to `Partition'` from [Problem 7-2](#id-7-2-quicksort-with-equal-element-values), part (b). The rest of the code of randomized quicksort uses this partitioning function instead of the ordinary version; also, the pivot is the first element in the subarray.

```
Fuzzy-Partition(A, p, r)
    x = A[p]    // Pivot is chosen to be at the beginning of A[p:r]. 
    i = p
    h = p
    for j = p + 1 to r
        if A[j].b < x.a
            y = A[j] 
            A[j] = A[h + 1]
            A[h + 1] = A[i]
            A[i] = y
            i = i + 1
            h = h + 1
        elseif A[j].a <= x.b
                // Mutually overlapping intervals including the pivot are treated as equal.
                // There could be many such joint sets of intervals, we select one of them.
            x.a = Max(A[j].a, x.a)
            x.b = Min(A[j].b, x.b)
            exchange A[h + 1] with A[j] 
            h = h + 1
    return i, h    // A[i:h] elements fuzzy-equal to x.
```

#### b.

Observe that as the intervals overlap more and more, the "equal" sector will grow. These intervals will be omitted from subsequent recursive calls. When all intervals overlap, then after calling `Fuzzy-Partition` once from the top level, the whole array becomes sorted. Therefore, the expected running time reduces to $$\Theta(n)$$. Otherwise, our algorithm runs in usual $$\Theta(n \lg n)$$ expected time.