An inductive proof shows that a statement holds in two steps: establish a base case, then show that one valid case implies the next. section 4.2
Climbing a ladder
To prove you can climb a ladder, start with the base case: your legs are on rung 1. Then use the inductive case: whenever you are on one rung, you can step onto the next. Repeating that step gets you to the top. section 4.2
An inductive proof follows this pattern:
- Base case: prove the statement for the starting values. section 4.2
- Inductive case: prove that validity for one size or case gives validity for the next. section 4.2
For quicksort, arrays of zero or one element are already sorted. If quicksort works for one array size, recursive calls can sort the smaller sub-arrays for the next size, so the method works for arrays of every size. section 4.2
def quicksort(array):
if len(array) < 2:
return array #1
else:
pivot = array[0] #2
less = [i for i in array[1:] if i <= pivot] #3
greater = [i for i in array[1:] if i > pivot] #4
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
#1 Base case: arrays with 0 or 1 element are already sorted.
#2 Recursive case
#3 Sub-array of all the elements less than the pivot
#4 Sub-array of all the elements greater than the pivot
A quicksort implementation labels its base and recursive cases directly. section 4.2
