COM 301
Lab 3: Comparing Sort Algorithms
Problem Description
We spent some time discussing performance of the algorithms, but in practice what one often wants to
test is how a given implementation performs on a given machine. You will write code for several
implementations of the sort algorithms and evaluate their performance.
Problem Solution and Guideline
The outline of your program should be as follows:
Generate an input array to be used for different sortimplementations.
For each of the implemented sort algorithms
o make a copy of the input array
o start the timer
o run the sort algorithm on the array
o stop the timer
o display the running time in milliseconds
Implementation Details
Generating Data
The program needs to generate an array (not an ArrayList) that you’ll sort using different methods. You
need to decide on the type of the array to use for testing. It is totally up to you. Your program needs to
populate the array with random values corresponding to whichever type you choose.
Before running each of the sort methods on the array, you should make a copy of it and run your
implementation of the algorithm on the copy. You have to make sure that each algorithm starts with the exact
same array as the previous one. You can use any language built-in procedure or library, if you wish.
Sorting Algorithms
You should implement four sorting algorithms: selection sort, merge sort, quick sort, and heap sort. You must
implement those using generic methods. Your implementation should follow the pseudo-code outlined in the
lectures or elsewhere.
Sorting and Timing
The program needs to measure the time it takes for each of your four methods to complete sorting for
several different sizes of the array.
It is up to you to:
either design a program that generates an array of a particular size and then run it multiple times,
or design a program that runs all different sizes on its own.
In either case, your program should not be interactive (no user input should be expected).
Use may use the C++ system time method to get the time before and after the call to the sort function. The
difference between the two will tell you how many nanoseconds it takes for the algorithm to complete its
task. You need to make sure that you use the appropriate time unit – milliseconds or nanoseconds.
Report
You need to write a short report based on multiple runs of your program using different sizes of the
array. Combine the numerical results into a table and produce graphs that demonstrate how the time
changes as a function of number of elements. Use the sample report image in the accompanying file
(project_3_Sample_Report.pdf) as a template for your report.Your report should include the tables and graphs from the sample report. It should also discuss what
you observed and if the results were as expected or not.
You should try to optimize your implementation and include the discussion of changes you made and
how they affected the time performance. Changes may sometimes decrease the performance - that’s
OK. You should try to explain why a particular change affected the time performance in a particular
way.
NOTE: The template for the tables and graphs contains the sizes of the arrays that you should use. If
your computer cannot handle the largest arrays (or it takes an extremely long time) you may stop
before.
Working on This Assignment
You should start right away! The code itself is not hard to develop, but you may want to spend some
time optimizing and fine-tuning you implementations. You also need to complete your code in time to
prepare the report and add improvements.
How and What to Submit
You should submit the report as a PDF document and all of the source code files in a single zip file.
Make sure that all the code is properly documented. All files have to contain a preamble that contains
your name. All the code should be your own.
Submit Lab 3 to the Assignment box no later than Sunday 11:59 PM EST/EDT.
Elements
Criteria
Score
Not Attempted
(Criterion is
missing, not in
evidence, or fails
to meet minimum
requirements.)
Novice
(Does not meet
expectations;
performance is
substandard.)
Basic
(Works towards
meeting
expectations;
performance needs
improvement.)
Proficient
(Meets
expectations;
performance is
satisfactory.).
Exemplary
(Exceeds
expectations;
performance
is
outstanding.)
Completeness and
correctness of the
report.
0-11
12-13
14-15
16-17
18-20
__/20
Code documentation.
0-10
11
12
13
14-15
__/15
Development and
correctness of the
application.
0-11
12-13
14-15
16-17
18-20
__/20
Development and
correctness of sorting
methods.
0-24
25-29
30-34
35-39
40-45
__/45
TOTAL ___/100
