Glimmer Labs

# Some Standard Sorting Algorithms

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

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.

To sort a list of values using selection sort
If the list is empty then
You're done
Otherwise
Identify small, the smallest value in the list
Remove small from the list
Sort the modified list
Shove small back 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.

To find the smallest value in a list (version 1: repetition)
Let guess be the first value in the list
For each value, val, in the list
If val < guess then
Let guess be val
guess is now the smallest value in the list
To find the smallest value in a list (version 2: recursion)
If the list contains only one element then
That element is the smallest value in the list
Otherwise
Let first be the first element in the list
Let guess by the smallest value in the remainder of the list
The smaller of guess and first is the smallest
value in the list

## Insertion Sort

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.

To sort a list, lst, using insertion sort
Create an empty list sorted
Insert each value in lst into the correct place in sorted

To insert each value in lst into the correct place in sorted
For each value, val in lst
Insert val into the correct place in sorted

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

To insert each value in lst into the correct place in sorted
If lst is empty then
You're done
Otherwise
Insert the first element in lst into sorted
Insert the remaining elements in lst into the new sorted

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.

To insert one value, val, at the proper position
in a sorted list, slist
Possiblity One: slist is empty
Make a list from val
Possiblity Two: val is less than or equal to
the forst value in slst
Add val to the front of slst
Possibility Three: val is greater than the first value
in slst
Keep the first value in slst and insert val into
the rest of slst

## Merge Sort

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.

To sort a 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.

To merge two sorted lists, slst1 and slst2
Possibility 1: slst1 is empty
Just use slst2
Possibility 2: slst2 is empty
Just use slst1
Possibility 3: The first element of slst1 is less than
element of slst2
Use the first element of slst1 as the first element
of the merged list.
Build the rest of the merged list by merging the rest of slst1
with slst2.
Possibility 4: The first element of slst1 is not less than
the first element of slst2
Use the first element of slst2 as the first element
of the merged list.
Build the rest of the merged list by merging the slst1
with the rest of slst2.

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 Labs: The Grinnell Laboratory for Interactive Multimedia Experimentation & Research
glimmer@grinnell.edu