CS 240: Lecture 18 – Sorting
Dear students:
Now that we have a new tool for analyzing recursive algorithms, we are ready to start looking at some of those algorithms. The fastest sorting algorithms are recursive. However, the fastest sorting algorithms are also complex. Rather than begin with them, we first look at some simpler but slower sorting algorithms.
Tail Recursion
Actually, we want to discuss one more recursion topic before we move to sorting. Last week we wrote this algorithm:
static boolean isPalindrome(int[] xs, int lo, int hi) {
if (lo > hi) {
return true;
} else if (xs[lo] != xs[hi]) {
return false;
} else {
return isPalindrome(xs, lo + 1, hi - 1);
}
}
We wrote it recursively because we were talking about analyizing recursive algorithms. If you can get yourself in the right frame of mind, a recursive solution tends to be more elegant than an iterative solution, but it’s usually more costly. Whenever you make recursive calls, you run into the danger of the stack filling up with stack frames and causing a stack overflow exception.
Turning this recursive solution into an iterative solution doesn’t take a lot of creativity. We could just wrap up the body inside a while loop and replace the recursive call with an adjustment to the parameters:
static boolean isPalindrome(int[] xs, int lo, int hi) {
while (true) {
if (lo > hi) {
return true;
} else if (xs[lo] != xs[hi]) {
return false;
} else {
++lo;
--hi;
}
}
}
Instead of pushing a new stack frame for the recursive call, this solution reuses the existing stack frame. While manual conversion to an iterative solution is an option, we can also build compilers that automatically perform the conversion. This automatic optimization only works if the recursive call is the only bit of computation left to perform in the current call. If anything is done with the recursive result, then the compiler will not perform this tail call optimization.
Does this function allow a tail call optimization?
function sum(list)
if list is []
return 0
else
return list.head.value + sum(list.tail)
We can rewrite this function so that it is tail recursive. Instead of accumulating via the return value, we accumulate in a second parameter:
function sum(list, sumSoFar = 0)
if list is []
return sumSoFar
else
return sum(list.tail, sumSoFar + list.head.value)
How about this one?
function contains(node, target)
if node is null
return false
else if target < node.value
return contains(node.left, target)
else if target > node.value
return contains(node.right, target)
else
return true
Sorting Exercises
Our investigation of the slower sorting algorithms will center on this set of exercises. Solve these on paper or tablet in order to get your thoughts visible. There’s nothing to turn in.
TODO
You have some work to do before the next class:
- Read sections 11.09-11.10 of OpenDSA.
- Keep working on the IntSet assignment. It’s due by the end of tomorrow. Remember you have teaching assistants available.
See you next time.
P.S. It’s time for a haiku!
They’re sorted by wealth
The rich ones all look the same
I think it’s the ties