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.
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 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
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
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