CSC151 2007S, Class 47: Introduction to Sorting
Admin:
* Updated instructions for submission of project
* Are there final questions on the project?
* I know that there have been some problems with region.compute-pixels!
I do not know how to resolve those problems efficiently.
* Exam 3 will be distributed tomorrow.
* Intentional mostly-talk class. (No lab!)
* EC: Percussion Ensemble 7:30 p.m. Friday (we think)
* EC: Women's Basketball 5:30 p.m. Friday vs. St. Norbert
* EC: Women's Basketball 1:00 p.m. Saturday vs. Carroll
* EC: George Cobb Statistics talk Monday noon
Overview:
* The problem of sorting.
* Writing sorting algorithms.
* Examples: Insertion, selection, etc.
* Formalizing the problem.
/What did we do on Tuesday?/
* Binary search things
* A technique for searching in which you look at half of the
region at once
* Works with vectors (not lists)
* Look at the middle and throw away half.
* A lot faster than looking at the elements one by one
* In order to use binary search, the vector must be in ascending order
*ANd you must be able to test for comparison
In order for binary search to work, the vector must be in order.
/THe problem of sorting: How?/
i
* Given a list or vector in no particular order, how do you get it in
order?
* Lists: Build a new, sorted version
* Vectors: Rearrange
* What techniques do we have for coming up with algorithms?
* Think about it
* Relate it to something you know how to do
* In "the real world"
* Previous algorithms you've written to solve similar problems
* Or that someone else has written
* Make sure that you understand the problem well
* Try to execute possible steps by hand
* Look at other solutions (not useful if you're solving something new)
* Look at common algorithm design techniques
First technique (credit to Lee and Gumm)a
* Insertion sort
* Separate your data into two parts: Unsorted and sorted
* Repeatedly
* Grab one element from unsorted
* Put it in the right place in sorted
* Bucket sort (credit to Decker)
* Pick logical groups into which to partition elements
(months for sorting by date, height ranges for sorting by height ...)
* Put each element into the proper group
* And then sort each group
* Selection sort (credit to Doers)
* Repeatedly
* Select the largest remaining element
* Put it at the end
Time to write one of these in Scheme.
;;; Procedure:
;;; list.sort
;;; Parameters:
;;; lst, a list to sort
;;; may-precede?, the order in which to sort
(define list.sort
(lambda (lst may-precede?)
...))
Time to call it
> (list.sort (list 156 2 1 5 8) <=)