CS Project 27
	Mr Rabbit sez: Enchiladas sound excellent! The Big Enchilada. The insertion sort.
Concepts	Activity	Homework

Review

We've learned how to traverse a list.

We've learned how to search a list.

We've learned how to alter a list-- deleting items, substituting items.

This lesson is The Big Enchilada for lists of simple data: Sorting a list.

Concepts

First of all, not all kinds of data are sortable. Symbols aren't.

In order to be sortable, a kind of data has to have some form of < defined for it.

Numbers do. Its called <

Strings do. Its called string<? And, if we are comparing all upper case, or all lower case, it's generally alphabetical order.

Chars do. Its called char<? It means which comes first in the character set. (Some time, do a web search and find a table of an ASCII character set. )

Symbols don't. This might strike you as strange, but that's just their nature. Symbols are either equal or unequal, and that's it.

There are a number of strategies for how to sort numbers. Roughly speaking, they fall into two families, selection sorts, and insertion sorts. There are some sorts that don't clearly fit in these families, but most do.

Selection sorts take the items from a list, sort of jumping around in the list-- selecting the items in order-- the smallest, then the next, and so on, to the largest-- and it builds a new list from beginning to end.

Insertion sorts generally just grab the first item from the list, and insert it into the right place in the list they're building.

We're going to develop an insertion sort. Actually, so that you don't have to reinvent the wheel, I'll tell you how to do it, and you code it up in Scheme.

The first essential thing here is that we are going to use the same template as usual.

The second essential thing is that we're going to need a helper function to insert one item into a (possibly empty) sorted list.

Developing an insertion sort

Here's a recursive definition for a sorted list of numbers

A sorted list of number (sorted-lon) is either

(cons num empty), or

(cons num sorted-lon)

where num is a number, and sorted-lon is a **sorted list of numbers such that every element is greater than num.

Now the strange thing about this definition is tells more than just the shape. There is a rule that always has to be enforced. This rule is called an invariant, because it must, well, "not vary".

I think I'm ready to write a purpose and contract:

; to sort a list
; insert-sort : nelon -> sorted-lon 
(define (insert-sort lon)...)

I've decided that the insert-sort function will consume a nelon (project 19), which is defined as:

A non-empty list of numbers (nelon) is either
1) (cons n empty)
2) (cons n a-nelon)

where n is a number and a-nelon is a **non-empty list of numbers.

So my function is going to be based on this definition!!!

So to make a sorted list, take you a little ol' nelon (call it L) , and:

• if the rest of L is empty (empty? (rest L))then produce the list with just the first element of L.
• if the rest of L isn't empty, then insert the first element of L into -- the **SORTED rest of L.

OK, the tricky thing is right there-- that wrinkle in the recursive step.

"Insert the first element into a sorted list" sounds messy enough that I'm going to make it a helper function.

(Remember the Rule of The Wish List? (Project 23) When a sub-task gets messy, give it a name and add it to the Wish List.)

So I drop what I'm doing, pull out my Magic Wish List Chalkboard, and write:

; to insert a number into a sorted-lon
; insert-one : num sorted-lon -> sorted-lon

When I design insert-one, I realize I have to follow the definition of an sorted-lon because that's what it will consume. So, the helper function, insert-one, will work like this:

To insert a number into an sorted-lon:

Either the number is bigger or smaller than the first element of the sorted-lon.

If it is smaller, or they're equal, then cons it onto the front of the sorted-lon.

If it is larger, then **insert the num into the rest of the sorted-list, and cons the first element of the (old) sorted-lon onto the front of that.

Start a file named L25.scm. Lesson #, name, title, date, vocabulary as usual.

Carefully follow design recipe #3, showing all the steps. Reuse code wherever possible.

Write a program named insert-sort which sorts a nelon.

I recommend that you base it on a nelon, and that you use a helper function for insert-one. You do not have to follow this advice.

You do, however, have to show the steps of the design recipe.

None, but if you have DrScheme at home, you may want to take some quiet time to think about this one.

When you get it running and tested, you deserve some enchiladas.

An Enchilada Platter from Chuy's in Austin, Texas.