Reading

These notes and closely review Unit 2 Section 1.

Quiz questions

Review quiz questions

We went over the quiz question, which asked you to give loop invariants for selectionSort and insertionSort.

sectionSort and insertionSort are generic

If you look at the sectionSort and insertionSort algorithms (and your loop invariants) you should see that the only assumption we make of them elements of the arrays we sort is that we have a valid "<" defined for them. What does that mean? Well, "<" must be a function that takes any two object of the type stored in $A$, and returns a true/false value. But not just any old boolean-valued function will do. It must be:
  1. transitive — i.e. we need $a \lt b$ and $b \lt c$ implies $a \lt c$
  2. anti-reflexive — i.e. $a \lt a$ must be false
You might be concerned that your invariants used $\leq$ rather than $\lt$. Fear not! Since $a \leq b \Leftrightarrow \neg(b \lt a)$ we can always recast the $\leq$'s in terms of $\lt$'s.
As long as the elements of $A$ have a valid $\lt$ defined, these algorithms work. Algoruithms like this are said to be generic.

Both are $\Theta(n^2)$, does that mean they run at the exact same speed?

Both sectionSort and insertionSort are $\Theta(n^2)$, does that mean they run at the exact same speed? No! We talked about how, when the asymptotic analysis yields the same results, we have to look at hidden constants to determine which will actually run faster. With smaller sized inputs, we might also have to look at lower-order terms and the thresholds implicit in our asymptotic notation.

Generalizing: the "Pick and Place" strategy

We talked about how sectionSort and insertionSort both follow a "pick and place" strategy. For insertionSort, the "pick" is trivial, and the "place" is complicated. For selectionSort, the "pick" is complicated, but the "place" is trivial. We could imagine creating new sorting algorithms by trying out new "pick" ideas and "place" ideas.

A new strategy: Divide & Conquer

One of the most generally useful strategies (or "paradigms") for efficient algorithm design is Divide & Conquer. We looked at the divide and conquer strategy in the problem of simple search in an unsorted array range. Here's what we came up with:
Algorithm: search(A,i,j,x) ← search for index in [i,...,j] at which x appears in A	

if i == j
  return A[i] == x ? i : NOTFOUND

m = (i + j)/2             ← divide

r1 = search(A,i,m,x)      ← conquer
r2 = search(A,m+1,j,x)

if r1 ≠ NOTFOUND          ← combine
  return r1
else
  return r2
      

Applying Divide & Conquer to sorting

Next we decided to try applying Divide and Conquer to the problem of sorting. This is where we got to:
Algorithm: sort(A,i,j)

if i == j
  return

m = (i + j)/2          ← divide

r1 = sort(A,i,m)       ← conquer
r2 = sort(A,m+1,j)

?????                  ← combine
      
So the question is, how do we efficiently combine these two sorted subarrays to form the sorted version of the original array?