Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Announcements

• New option to avoid cortland and the Mac lab. JDK 1.5 on FreeBSD.
• Advance warning: our first exam is October 19 during lab period.
• There will be an opportunity to ask exam-related questions each day up until our exam. If there is interest in a review session, we can arrange a time Monday or Tuesday evening.

Agenda

• Lab 4 out - due Wednesday because of reading period.
• Comparable objects
• Sorting
  • Bubble Sort
  • Selection Sort
    • recursive implementation
    • correctness proof
    • complexity proof

Links

• Visit your favorite search engine to find Java applets that visualize these sorting techniques.

Examples

• BinSearch
• Swap
• SelectionSort

Correctness Proof for recSelSort

To prove correctness of a procedure like our recursive selection sort, we use a form of proof by mathematical induction:

1. Prove base case(s). (Usually this is trivial)
2. Show that if algorithm works correctly for all simpler (i.e., smaller) input, then will work for current input.

To show that the recSelSort algorithm given earlier is correct, we will reason by induction on the size of the array (i.e. on lastIndex)

Base: If lastIndex <= 0 then at most one element in elts, and hence sorted - correct.

Induction Hypothesis: Suppose it works if lastIndex < n.

Induction: Show it works if last = n (> 0).

The for loop finds largest element and then swaps it with elts[lastIndex].

Thus elts[lastIndex] holds the largest element of list, while others are held in elts[0..lastIndex-1].

Since lastIndex- 1 < lastIndex, know (by induction hypothesis) that recSelSort(lastIndex-1,elts) sorts elts[0..lastIndex-1].

Because elts[0..lastIndex-1] in order and elts[lastIndex] is >= all of them, elts[0..lastIndex] is sorted.

Success.

Complexity Proof for recSelSort

Claim: recSelSort(n-1,elts) (i.e, on n elements) involves n*(n-1)/2 comparisons of elements of array.

Base: n = 0 or 1, 0 comparisons and n*(n-1)/2 = 0.

Induction hypothesis: Suppose recSelSort(k-1,elts) takes k*(k-1)/2 comparisons for all k < n.

Induction step: Show that it's true for n as well.

Look at algorithm: Run algorithm on recSelSort(n-1,elts). Therefore, last = n-1.

Go through for loop "last" = n-1 times, w/ one comparison each time through.

Thus n-1 comparisons. The only other comparisons are in the recursive call: recSelSort(last-1,elts) where last = n-1.

But by induction (since last < n), this takes last*(last-1)/2 = (n-1)*(n-2)/2 comparisons.

Therefore, altogether we have (n-1) + (n-1)*(n-2)/2 = (n-1)*2/2 + (n-1)*(n-2)/2 = (n-1)*(2 + n-2)/2 = (n-1)*n/2 = n(n-1)/2 comparisons.

Finished proof.

Therefore recSelSort takes O(n²) comparisons.