Week 6: Lab Document, 10/4


Searching and sorting are two of the most basic and important computational tasks that computer programs need to perform. We have already talked a bit about searching and this lab gets you started on sorting. Note that Project 1 requires that you produce sorted output; this lab might help in that regard.

Some of the most well-known algorithms for sorting are:

  1. insertion sort,
  2. bubble sort,
  3. selection sort,
  4. merge sort,
  5. quick sort, and
  6. heap sort.

Later in the semester, we'll study the last three algorithms in the above list. The first three algorithms are extremely simple, but also somewhat inefficient. Follow the links posted above and study these algorithms.

Problem: Implement insertion sort, bubble sort, and selection sort and compare their running times. What do you conclude about the relative speeds of these algorithms based on this experimental comparison?