CSC161 Programming Assignment 2: Sorting
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
- Implement the
copyArray
function inpa1.cpp
- Implement at least one slow and one fast sorting function in
sort.hpp
- Update the required places in
pa1.cpp
(indicated byTODO
) - 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:
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.
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 thetemplate <class T>
line above each definition, just like we have above each declaration insort.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 ofints
orstrings
or anything else specific. Rather, its elements are of typeT
, whereT
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 namedelm
, which is of typeT
. - 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 tolist
. 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?".