[Skip Links]

**Sorting:**
[Front Door]
[Syllabus]
[Standard Sorting Algorithms]
[Lab Manual (PDF)]

**Exercises:**
[PBJ]
[PBJ2]
[Sorting CDs]
[Sorting Numbers]
[Starting Scheme]
[Comparing Algorithms]
[Selection Sort]
[Formalizing Requirements]
[Comparing Sorts]
[Finding the Largest]

**Glimmer/Education:**
[Glimmer Labs]
[SchemeWeb]
[ScriptFu For Schemers]
[CS Education]

Glimmer Labs

The problem of putting a collection of values in order appears so frequently that it's one of the most commonly studied problems in computer science. As with many problems, it has many different potential solutions. In this document, we consider a few of the standard algorithms that computer scientists have developed over the years.

As you read through these algorithms, you might want to try running them by hand to see how (and whether) they work.

*Selection sort* relies on your ability to easily identify
the smallest value in the collection. To sort using selection sort,
you repeatedly (1) identify the smallest value and (2) put it at the
front of the values not yet identified. We can naturally phrase this
algorithm recursively.

Tosorta list of values using selection sort If the list is empty then You're done Otherwise Identifysmall, the smallest value in the list Removesmallfrom the list Sort the modified list Shovesmallback on the front of the sorted list

Of course, for this algorithm to work, we need a way to find the smallest value in a list and to remove an element from a list. We'll consider finding the smallest value and leave removal as a thought problem.

It's fairly easy to find the smallest value in a list. Here are two techniques, one using repetition and one using recursion.

Tofind the smallest valuein a list (version 1: repetition) Letguessbe the first value in the list For each value,val, in the list Ifval<guessthen Letguessbevalguessis now the smallest value in the list

Tofind the smallest valuein a list (version 2: recursion) If the list contains only one element then That element is the smallest value in the list Otherwise Letfirstbe the first element in the list Letguessby the smallest value in the remainder of the list The smaller ofguessandfirstis the smallest value in the list

Insertion sort works by building the sorted list from the bottom up. We repeatedly take the first element from the list to be sorted and put it in the correct place in the sorted list.

Tosorta list,lst, using insertion sort Create an empty listsortedInsert each value inlstinto the correct place insortedToinsert each valueinlstinto the correct place insortedFor each value,valinlstInsertvalinto the correct place insorted

Note that we might also want to phrase a key step in insertion sort recursively.

Toinsert each valueinlstinto the correct place insortedIflstis empty then You're done Otherwise Insert the first element inlstintosortedInsert the remaining elements inlstinto the newsorted

In either case, we rely on a helper procedure. This time, the goal of the procedure is to insert a value into a sorted list.

Toinsert one value,val, at the proper position in a sorted list,slistPossiblity One:slistis empty Make a list fromvalPossiblity Two:valis less than or equal to the forst value inslstAddvalto the front ofslstPossibility Three:valis greater than the first value inslstKeep the first value inslstand insertvalinto the rest ofslst

Both selection sort and insertion sort build the sorted list one
element at a time. As you get more experience in computer science,
you'll quickly learn that there are sometimes better ways to break
up your work. The *divide-and-conquer* technique suggests
breaking your work in half (or other large parts). We can use that
technique along with recursion to come up with a sorting algorithm
called

.
*Merge Sort*

Tosorta list using merge sort Split the list into two equal halves (or as equal as possible) Sort each half Merge the two halves together

Once again, we rely on some helper algorithms. We need a way to split the list in half and a way to merge two sorted lists into one sorted list. We'll leave splitting as an exercise to the reader. Merging is somewhat more interesting.

Tomergetwo sorted lists,slst1andslst2Possibility 1:slst1is empty Just useslst2Possibility 2:slst2is empty Just useslst1Possibility 3: The first element ofslst1is less than element ofslst2Use the first element ofslst1as the first element of the merged list. Build the rest of the merged list by merging the rest ofslst1withslst2. Possibility 4: The first element ofslst1is not less than the first element ofslst2Use the first element ofslst2as the first element of the merged list. Build the rest of the merged list by merging theslst1with the rest ofslst2.

This document was generated by
Siteweaver on Mon Aug 18 20:19:15 2003.

The source to the document was last modified on Tue Aug 20 11:36:16 2002.

This document may be found at `http://glimmer.cs.grinnell.edu/Sorting/sorting-overview.html`

.

You may wish to validate this document's HTML ; ; Check with Bobby

glimmer@grinnell.edu