## Computer Science 136 |

**Lecture 11: Comparable Objects, Sorting****Date: October 3, 2005**

- 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.

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

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

- BinSearch
- Swap
- SelectionSort

* *

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

- Prove base case(s). (Usually this is trivial)
- 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

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

Success.

* *

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 ^{2})* comparisons.