Held Friday, November 17, 2000
Summary
Today we move on to algorithm design for a very common problem, that
of sorting. When you sort an array or vector, you put the
elements in order (e.g., alphabetical, numerical, ...).
Notes
- I've decided not to add any more homework stress to your lives. Hence,
any remaining homeworks will be based on labs.
- The searching lab is due
next Wednesday.
- Since I didn't end up giving separate lab writeups as assignments,
I've updated the grading scale. Homework is still worth 30%, and
includes the lab writeups. Class participation is still worth 10%.
I'll probably give you a chance to grade each other on class
participation :-)
- I'll be gone on Monday. Mr. Walker will run a lab on sorting. I'll
email you about the readings for Monday and Tuesday. I'd appreciate
it if you do each reading on time.
- Have a great weekend!
Overview
- The problem
- Examples using various objects
- Describing the problem
- Famous solutions
- Typically, computer scientists look at collections of problems and
attempt to find appropriate generalizations of these problems
(or their subproblems).
- By solving the generalized problem, you solve a number of
related problems.
- One problem that seems to crop up a lot is that of sorting.
Given a list, array, vector, sequence, or file of comparable elements,
put the elements in order.
- in order typically means that each element is no bigger than
the next element. (You can also sort in decreasing order, in
which case each element is no smaller than the next element.)
- you also need to ensure that all elements in the original
list are in the sorted list.
- you also need to ensure that no other elements are in the list.
- We'll look at techniques for sorting vectors and lists.
- In my experience, most of us know some sorting algorithms, but
have difficulty generalizing them.
- I'll bring in some things to sort (most frequently, a stack of CDs)
and we'll look at different ways to sort them.
- Before moving on to algorithms for solving the sorting problem, let's
take a look at the way wemight document one (or all) of the
procedures
- Purpose?
- Parameters?
- Produces?
- Preconditions?
- Postconditions?
- One simple sorting technique is insertion sort.
- Insertion
sort operates by segmenting the list into unsorted and sorted portions,
and repeatedly removing the first element from the unsorted portion
and inserting it into the correct place in the sorted portion.
- This may be likened to the way typical card players sort their
hands.
- What's the extra storage? It should be constant.
- How might we code this recursively?
- Selection sort is among the simpler and more natural
methods for sorting.
- In this sorting algorithm, you segment the array into two
subparts, a sorted part and an unsorted part. You repeatedly find the
largest of the unsorted elements, and swap it into the
beginning of the sorted part. This continues until there are no
unsorted elements.
- Here's a potentially-helpful picture:
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
|
Unsorted Sorted
- Note that we can also write selection sort iteratively.
- Bubble sort is a lot like both insertion sort and selection sort
- In bubble sort, you step all the way through the array, swapping
adjacent elements if they're out of order.
- This ``bubbles'' the largest value to the end.
- Like selection sort, it puts the largest value at the end. It just
uses a different technique.
- Like insertion sort, it repeatedly swaps neighboring elements when
they're out of order. Unlike insertion sort, it goes all the way
through the array.
- There's an interesting variant of bubble sort that requires multiple
simultaneous swaps. We'll simulate it in class if there's enough time.