Towers of Hanoi

• \(S(0) = 0\)
• \(S(1) = 2 \times 0 + 1 = 1\)
• \(S(2) = 2 \times 1 + 1 = 3\)
• \(S(3) = 2 \times 3 + 1 = 7\)
• etc

What do we notice?

Project 3

• Questions?
• Demos start this week
  • Sign up on BrightSpace!

Pseudocode / running time

The algorithm we used was called the “Bubble Sort” algorithm. It’s called this because the bigger elements “bubble up” to the top at each iteration.

Exercise: Write pseudo-code for the algorithm we described.

Selection Sort

Here we describe another algorithm to sort. This algorithm uses the fact that it’s easy to find the smallest element in a list.

• For each \(i\), look for the smallest element in the list between \(i\) and the end of the list.
• If we find something smaller than \(a_i\), swap it with the smallest element between \(i\) and the end.
• Repeat this until we have looked through all \(i\) from \(0\) to \(n - 1\).

Write pseudocode for this algorithm.

Running times

Analyze the running times of the two algorithms. Is one better than the other in terms of Big Oh? Fill in the table:

\[ \begin{array}{|c|c|} \hline \text{Algorithm} & \text{Running Time} \\ \hline \text{Bubble Sort} & \\ \hline \text{Selection Sort} & \\ \hline \end{array} \]

Upshot

• Can we do any better?
• Yes, but requires a new technique: recursion!