Contents

Overview

There are several goals of this assignment, including learning how to use namespaces, function templates, and pass functions as parameters. You will implement at least one slow sorting algorithm (bubble, insertion, or selection sort) and one faster sort (quick or merge sort) and time them. The idea is to understand how much faster the fast sorts are over the slower sorts.

The program skeleton I provide will start off by randomly generating an array of different sizes. A copy of each array will be made and one copy sent to each sorting method. The method will be timed (I will explain how to do that in the code.) You will have to finish implementing the copy function, the timing code, and the sorting methods.

Here's an example of my version of PA2 running:

$ ./pa2 
Array size 100: 
  Slow sort (avg. clock ticks): 58.22
  Fast sort (avg. clock ticks): 23.39
Array size 1000: 
  Slow sort (avg. clock ticks): 3928.42
  Fast sort (avg. clock ticks): 172.03
Array size 10000: 
  Slow sort (avg. clock ticks): 445690
  Fast sort (avg. clock ticks): 1971.1

In this case, I used bubble sort and merge sort. It's very clear that for even moderately sized lists (an array of 10,000 numbers isn't really that big), bubble sort's O(n2) complexity makes it incredibly slow. Here's a graph (with a few extra array sizes thrown in) that makes the comparison even more evident:

(Back to top)

Requirements

Here's a skeleton to get you started:

sort.h
sort.hpp
pa2.cpp
(Back to top)

Extra credit

Make sure you indicate in your program header (in the description) whether you've attempted the extra credit, otherwise I won't count it!!!

EC-1 (1 point)

Implement an additional sort function. You will get 1 point per extra sort function.

EC-2 (2 point)

Increase the number of different array sizes—don't make them too big as it'll take too much time to sort them. Then, plot the performance of the sorting algorithms. Be sure to include a graph title, axis labels, and a key for the lines. Include the plot as a .png file on Canvas.

(Back to top)

Submissions

Everything should be uploaded to Canvas by the deadline posted.

(Back to top)

Hints

Last updated: 21-Feb-2014 8am