Trying to understand this Quicksort Correctness proof

ignougroup
Problem Detail: 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. enter image description here 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

Asked By : FrostyStraw

Answered By : Rick Decker

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 $nin {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 $nge 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63666