Exercise: Comparing Sorting Algorithms

Selection sort is not the only well-know sorting algorithm. Other common ones include insertion sort and merge sort. Which is best? Let's try to figure out experimentally (a) how each does on a variety of different kinds of inputs and (b) what the approximate curve is for the running time of each.

You can load an implementation of selection sort with

(load "/home/rebelsky/Web/Scheme/simple-selection-sort.ss")

That Scheme file provides the procedures

(selection-sort lst)
(smallest lst)
(remove val lst)

You can load an implementation of insertion sort with

(load "/home/rebelsky/Web/Scheme/simple-insertion-sort.ss")

That Scheme file provides the procedures

(insertion-sort list)
(insert val lst)

You can load an implementation of merge sort with

(load "/home/rebelsky/Web/Scheme/simple-merge-sort.ss")

That Scheme file provides the procedures

(merge-sort lst)
(merge slst1 slst2)
(split lst)

Using the techniques you've developed for evaluating the running time of selection sort, compare the running times of selection sort, insertion sort, and merge sort. Which is fastest on large problems? On small? How much faster? Does it matter if we start with a sorted list? With a reverse-sorted list?

Note that you may have difficulty finding a quadratic function that matches the running time of merge sort. You might want to try other functions to see if you can get a better fit.

This document was generated by Siteweaver on Tue Aug 17 07:43:10 2010.
The source to the document was last modified on Tue Aug 17 07:41:45 2010.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Glimmer/Sorting/comparing-sorts.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