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(n²) 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

• Implement the copyArray function in pa1.cpp
• Implement at least one slow and one fast sorting function in sort.hpp
• Update the required places in pa1.cpp (indicated by TODO)
• Run your code and add the output to the top of pa1.cpp in the header where it says // Output :
• Read over the program and make sure you understand everything that's happening. Ask questions if you don't. You are responsible for understanding what's going on, and I may quiz or test you on it.
• Everything in the rubric (posted on Canvas) should be followed
• Make sure to follow the style guidelines

Here's a skeleton to get you started:

(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

• In sort.hpp, you need to define your sorts with templates. That means you need to have the template <class T> line above each definition, just like we have above each declaration in sort.h. For example, the definition for bubble sort would look like this:
• Another point about templates. The whole point of the sort functions in the sort namespace is that they are templated. That means the input list is not strictly a list of ints or strings or anything else specific. Rather, its elements are of type T, where T is decided at compile time. For example, we could do: T elm = list[0];—that would store the first element of the list in a variable named elm, which is of type T.
• The parameter list to the sorting functions is a reference to a pointer, or, said differently, a reference to an array. This allows us to reassign a new array to list. For more information, see the section on pointers int he C++ review. Specifically, look at the example below the paragraph that starts: "Now, what if we want to pass a pointer by reference?".