Trying to understand this Quicksort Correctness proof

Question

This proof is a proof by induction, and goes as follows:

P(n) is the assertion that "Quicksort correctly sorts every input array of length n."

Base case: every input array of length 1 is already sorted (P(1) holds)

Inductive step: fix n => 2. Fix some input array of length n.

Need to show: if P(k) holds for all k < n, then P(n) holds as well

He then draws an array A partitioned around some pivot p. So he draws p, and calls the part of the array that is < p as the 1st part, and the part that is > p is the second part. The length of part 1 = k1, and the length of part 2 is k2. By the correctness proof of the Partition subroutine (proved earlier), the pivot p winds up in the correct position.

By inductive hypothesis: 1st, 2nd parts get sorted correctly by recursive calls. (Using P(K1),P(k2))

So: after recursive calls, entire array is correctly sorted.

QED

My confusion: I have a lot of problem seeing exactly how this proves the correctness of it. So we assume that P(k) does indeed hold for all natural numbers k < n.

Most of the induction proofs I had seen so far go something like: Prove base case, and show that P(n) => P(n+1). They usually also involved some sort of algebraic manipulation. This proof seems very different, and I don't understand how to apply the concept of Induction to it. I can somewhat reason that the correctness of the Partition subroutine is the key. So is the reasoning for its correctness as follows: We know that each recursive call, it will partition the array around a pivot. This pivot will then be in its rightful position. Then each subarray will be further partitioned around a pivot, and that pivot will then be in its rightful position. This goes on and on until you get an subarray of length 1, which is trivially sorted.

But then we're not assuming that P(k) holds for all k < n....we are actually SHOWING it does (since the Partition subroutine will always place one element in its rightful position.) Are we not assuming that P(k) holds for all k

Answer 1

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with.

The proof you describe is known as the principle of strong mathematical induction and has the form

Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that

1. $P(1)$ is true, and

2. $(\forall k < n \;[P(k)])\Longrightarrow P(n)$

Then $P(n)$ is true for all integers $n\ge 1$.

In the proof to which you refer, that's exactly what's going on. To use quicksort to sort an array of size $n$, we partition it into three pieces: the first $k$ subarray, the pivot (which will be in its correct place), and the remaining subarray of size $n-k-1$. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.

We show this is correct by strong induction: since the first subarray has $k<n$ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has $n-k-1<n$ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.

Answer 2

This proof uses the principle of complete induction:

Suppose that:

• Base case: $P(1)$
• Step: For every $n > 1$, if $P(1),\ldots,P(n-1)$ hold (induction hypothesis) then $P(n)$ also holds.

Then $P(n)$ holds for all $n \geq 1$.

You can prove this principle using the usual induction principle by considering the property $$ Q(m) \Leftrightarrow P(1) \text{ and } P(2) \text{ and } \cdots \text{ and } P(m) $$ I leave you the details.

---

Now, let's use complete induction to prove that the following version of Quicksort sorts its input correctly:

Quicksort(A, n)
    if n = 1 then:
        return
    else:
        let X[1...x] consist of all elements of A[2],...,A[n] which are at most A[1]
        let Y[1...y] consist of all elements of A[2],...,A[n] which are larger than A[1]
        call Quicksort(X, x)
        call Quicksort(Y, y)
        set A to the concatenation of X, A[1], Y

Here A[1],...,A[n] is the input array, and n is its length. The statement that we want to prove is as follows:

Let $A$ be an array of length $n \geq 1$. Denote the contents of $A$ after calling Quicksort by $B$. Then:

1. Quicksort terminates on $A$.
2. There is a permutation $\pi_1,\ldots,\pi_n$ of $1,\ldots,n$ such that $B[i] = A[\pi_i]$.
3. $B[1] \leq B[2] \leq \cdots \leq B[n]$.

I will only prove the third property, leaving the rest to you. We thus let $P(n)$ be the following statement:

If $A$ is an array of length $n \geq 1$, and $B$ is its contents after running Quicksort(A, n), then $B[1] \leq B[2] \leq \cdots \leq B[n]$.

The proof is by complete induction on $n$. If $n = 1$ then there is nothing to prove so suppose that $n > 1$. Let $X,x,Y,y$ be as in the procedure Quicksort. Since $x,y < n$, the induction hypothesis shows that $$ X[1] \leq X[2] \leq \cdots \leq X[x] \\ Y[1] \leq Y[2] \leq \cdots \leq Y[y] $$ Moreover, from the way we formed arrays $X$ and $Y$, it follows that $X[x] \leq A[1] < Y[1]$. Thus $$ X[1] \leq \cdots \leq X[x] \leq A[1] < Y[1] \leq \cdots \leq Y[y]. $$ It follows immediately that $B[1] \leq \cdots \leq B[n]$. Thus $P(n)$ holds.

Answer 3

The missing part of the argument is transitivity of '<' - i.e the property that if a < b and b < c, then a < c. The proof that the final array is sorted goes something like this:

Let A[i], A[j] be elements of the array post-sort, where i < j. Then A[i] < A[j] follows from one of the following placement cases (and there are no other cases):

(a) i and j are in the first partition - A[i] < A[j] follows by recursion/induction.

(b) i and j are in the second partition - A[i] < A[j] follows by recursion/induction.

(c) i is in the first partition and j is the index of the pivot - A[i] < A[j] follows by proof of partition procedure.

(c) i is the index of the pivot and j is in the second partition - A[i] < A[j] follows by proof of partition procedure.

(e) i is in first partition and j is in second partition - then by partition procedure, A[i] < pivot, and pivot < A[j]. So by transitivity, A[i] < A[j].