Chapter 4
I
Quicksort
For example, suppose you pick 3 as the pivot. You call quicksort on the
sub-arrays.
The sub-arrays get sorted, and then you combine the whole thing to get
a sorted array. This works even if you choose 5 as the pivot.
This works with any element as the pivot. So you can sort an array
of five elements. Using the same logic, you can sort an array of six
elements, and so on.
65
Quicksort
Here’s the code for quicksort:
def quicksort(array):
if len(array) < 2:
return array
Base case: arrays with 0 or 1 element are already “sorted.”
else:
pivot = array[0]
Recursive case
less = [i for i in array[1:] if i <= pivot]
Sub-array of all the elements
less than the pivot
greater = [i for i in array[1:] if i > pivot]
Sub-array of all the elements
greater than the pivot
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
Inductive proofs
You just got a sneak peak into
inductive proofs!
Inductive proofs are one
way to prove that your algorithm works. Each inductive proof has two
steps: the base case and the inductive case. Sound familiar? For example,
suppose I want to prove that I can climb to the top of a ladder. In the
inductive case, if my legs are on a rung, I can put my legs on the next rung.
So if I’m on rung 2, I can climb to rung 3. That’s the inductive case. For
the base case, I’ll say that my legs are on rung 1. Therefore, I can climb the
entire ladder, going up one rung at a time.
You use similar reasoning for quicksort. In the base case, I showed that the
algorithm works for the base case: arrays of size 0 and 1. In the inductive
case, I showed that if quicksort works for an array of size 1, it will work
for an array of size 2. And if it works for arrays of size 2, it will work for
arrays of size 3, and so on. Then I can say that quicksort will work for all
arrays of any size. I won’t go deeper into inductive proofs here, but they’re
fun and go hand-in-hand with D&C.
|
