Procedure Quicksort2(L 0:N 1 , Low, High) Recursive

Induction Template

Your induction proofs should always utilize the following template:

“We prove [statement of what you want to prove correct ] by [either weak or strong] induction on [an appropriate integer variable, say m].

Basis step: [usually m = 0 or m = 1]

Induction step: [Assume true for all km (strong form) or for m – 1 (weak form), and then show it must be true for m]

Improved QuickSort and Correctness Proof

As an illustration of the use of induction, we prove the correctness of the following version of QuickSort.

procedureQuickSort2(L[0:n – 1],low,high) recursive

Input:L[0:n – 1] (a list of size n)

Output:L[low:high] sorted in increasing order

whilelowhighdo

Partition(L[0:n – 1],low,high,p)

ifp– low≥high– p then

QuickSort2(L[0:n – 1],p+1,high)

high ← p– 1

else

QuickSort2(L[0:n – 1],low, p– 1)

low ← p+1

endif

endwhile

endQuickSort2

Correctness Proof for QuickSort2.

We prove that QuickSort2 is correct by strong induction on high– low. We assume that Partition is correct.

Basis step: high – low = 0. Then low = high and the while loop is skipped, so that QuickSort2 returns with no action taken. Thus, in particular, the single element L[low:low] (and everything else) is unchanged, so thatQuickSort2 is correct and the basis step is established.

Induction step: Assume that QuickSort2 is correct wheneverhigh – lowk, and assume that it is called with high – low = k > 1.

Now consider what happens after the first iteration of the while loop. After the call to Partition, the list L[low: high] has the property that every element in L[low: p – 1] is not larger than L[p], and every element in L[p+1: high] is not smaller than L[p] (where low ≤ p ≤ high). Additionally, every list element in L[0: n – 1] whose index is outside the range [low: high] is unchanged. Then eitherQuickSort2(L[0:n – 1],p+1,high) is called, orQuickSort2(L[0:n – 1],low, p– 1) is called. In either case, the new values of low and high have a difference that is smaller than k, so by induction hypothesis, either L[p: high] is sorted (with L[low: p – 1] remaining unchanged), or L[low: p – 1] is sorted(with L[low: p – 1] remaining unchanged). Suppose for definiteness that it is the first case (the other case has a completely similar argument). Now note that for the reminder of execution of the algorithm, QuickSort2 works identically as if it was called originally with low = low and high = p – 1. Thus, by induction hypothesis, QuickSort2 will sort L[low: p – 1] (and leave L[p: high] alone), so that the entire list L[low: high] (with the original values of low and high) will be sorted. This completes the induction.