Class 47: Sorting with Divide and Conquer

Held Tuesday, November 21, 2000

Summary

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.

Notes

• 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.

Overview

• Review
• Idea: Divide and conquer sorting
  • Techniques for dividing
• Merge sort
• Quicksort

Examples

• 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 call-with-values, but that seems somewhat extreme.
• In Scheme

  (define dac-sort
    (lambda (lst)
      (letrec ((divide ...)
               (join ...))
        (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!

Merge Sort

• 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 together.
• Essentially, we look at the smallest value in each half and pick that one next as we put them into our sorted list.

Quick Sort

• 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?

Coding Merge Sort

• Intentionally left blank so that we can develop the code together.