teaching machines

CS 240: Lecture 18 – Sorting

October 4, 2021 by . Filed under cs3, fall-2021, lectures.

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:

See you next time.

Sincerely,

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