Correctness Proof for recSelSort

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.

Correctness Proof for recSelSort