Held Tuesday, November 21, 2000
Today we revisit the question of sorting by considering some sorting
algorithms that are typically more efficient than insertion sort.
These algorithms depend on the divide and conquer strategy
that we used so successfully in binary search.
- How did Monday's class go?
- The at a glance sheet managed
to get out of date. I think that it's now correct.
- Don't forget, the lab on searching
is due tomorrow.
- I'll have one or two more labs due this semester.
- It looks like you'll need to wait until after Thanksgiving to get the
1st exam back. I'm very very sorry for that delay. It has not been the
easiest of semesters for me.
- Idea: Divide and conquer sorting
- Merge sort
- It turns out that insertion sort (and selection sort and bubble sort)
are not the fastest sorting algorithms that computer scientists have
come up with.
- In fact, the divide and conquer process that we applied
in developing binary search works equally well for sorting.
- We'll use a stack of books from the bookshelf today and sort
them by number of pages.
- To sort a group of things (vector or list)
- Divide that group in half (How?)
- Sort each half (oh boy, recursion!)
- Put the sorted halves back together (How?)
- We'll assume that the divide procedure returns a pair of lists.
- I could also return two lists and then use
but that seems somewhat extreme.
- In Scheme
(letrec ((divide ...)
(let* ((divided (divide lst))
(first (car divided))
(second (cdr divided)))
(join (dac-sort first) (dac-sort second))))))
- As you might guess, I'm going to ask you how to divide the group
in half and how to put the sorted halves back together.
- Don't look ahead in the outline!
- In merge sort, we divide the group in a fairly straightforward
way: the first half of the things in the current ordering and
the second half of the things in the current ordering.
- Once we've finished sorting the two halves, we have two nicely
sorted halves, but may have some difficulty putting them back
- Essentially, we look at the smallest value in each half and pick
that one next as we put them into our sorted list.
- In Quicksort, we also divide the group in a straightfoward way:
into small things and big things.
- Once we've finished sorting the two halves, we just need to
append them together.
- But how do we divide the group?
- Intentionally left blank so that we can develop the code together.