SUNY Geneseo Department of Computer Science

Induction, Part 2

Return to List of Lectures

Questions?

Induction

kth smallest element in an unsorted array A[1..n]

• Precondition: 0 < k ≤ ( last - first + 1 )

        kthSmallest( A, first, last, k )
            if last < first
                // array section is empty, error!
            else
                p = partition( A, first, last )      // as in Quicksort
                if k < p-first+1
                    kthSmallest( A, first, p-1, k )
                else if k > p-first+1
                    kthSmallest( A, p+1, last, k-(p-first+1)
                    // BUG - k+p doesn’t make sense—changed above to k-(p-first+1)
                else
                    return A[p]

• Second recursive call to kthesmallest should pass a k parameter that reflects the number of small elements before the right-hand section of the array

• Algorithm is now fixed and proven correct for the cases k < p-first+1 and k > p-first+1. Last case is k = p-first+1, in which case p indexes the kth element in the section, and partition has put the kth-smallest element in that position, so returning A[p] is correct.

Quicksort

• Prove that Quicksort is correct, assuming that its partitioning function is
• Precondition: first ≤ last

        quicksort( A, first, last )
            if first < last
                p = partition( A, first, last )
                    // Assume that here A[first..p-1] ≤ A[p] ≤ A[p+1..last]
                quicksort( A, first, p-1 )
                quicksort( A, p+1, last )

• Postcondition: A[first..last] is sorted
• Prove correctness by induction on n, the size of the array section
• Base case: n = 1. In this case first = last, so quicksort does nothing, which is correct since a list of 1 element is necessarily sorted
• Induction hypothesis (strong induction): Assume A[first..last] is sorted after quicksort returns for any section with size ≤ k ≥ 1.
• Induction step: Consider an array section of size k+1.
  • In this case first < last, so partition divides the array into sections as described by the comment above.
  • The two recursive calls then each have sections of size no more than k, because at least element p is taken out of each recursive section. Therefore each call sorts its section, by the induction hypothesis.
  • The original section thus ends up containing elements less than or equal to A[p], sorted, followed by A[p], followed by elements greater than or equal to A[p] sorted, i.e., the whole section is sorted

Next

Execution time analysis for divide-and-conquer

• Read section 4.5
• Background: section 2.3.2

Exam 1 moves to Thursday 2/28