Assignment 2 five sorting algorithms

Programming Assignment 2 (200 points)

• Objective
In this assignment, you will implement five sorting algorithms: selection sort, insertion sort, bubble sort, shell
sort and radix sort in C++. You will test your code using varied input cases, time the implementation of sorts,
record number of comparisons performed in the sorts, and compare these computational results with the running
time of implemented algorithms using Big-O asymptotic notation. You will be required to manage this project
with GitHub.
• General Guidelines
1. This project can be done in groups of at most three students. Please use the cover sheet at the previous
page for your hardcopy report.
2. The supplementary program is packed in 221-A2-code.tarwhich can be downloaded from the course
website. You need to “untar” the file using the following command on linux:
tar xfv 221-A2-code.tar
It will create the directory 221-A2-code. You will be required to push the files in this directory to your
team’s repository. For more information on this, see the Git tutorial.
3. Make sure that your code can be compiled using a C++ compiler running on a linux machine before
submission because your programs will be tested on such a linux machine. UseMakefile provided in the
directory to compile C++ files by typing the following command:
make
You may clean your directory with this command:
make clean
4. When you run your program on a linux machine, use Ctrl+C (press Ctrl with C) to stop the program. Do
NOT use Ctrl+Z, as it just suspends the program and does not kill it. We do not want to see the department
server down because of this assignment.
5. Supplementary reading
(a) Lecture note: Introduction to Analysis of Algorithms
(b) Lecture note: Sorting in Linear Time
(c) Git tutorial
6. Submission guidelines
(a) Electronic copy of all your code, 15 types of input integer sequences, and reports in LyX and PDF
format should be in the directory221-A2-code. This command typed in the directory 221-A2-code
will create the tar file (221-A2-code-submit.tar) for the submission to CSNet:
make tar
(b) Your program will be tested on TA’s input files.
• Code
1. In this assignment, the sort program reads a sequence of integers either from the screen (standard input) or
from a file, and outputs the sorted sequence to the screen (standard output) or to a file. The program can
be configured to show total running time and/or total number of comparisons done in the sort.
2. This program does not have a menu but takes arguments from the command line. The code for interface
is completed in the template programs, so you only have to know how to execute the program using the
command line.
2
The program usage is as follows. Note that options do not need to be specified in a fixed order.
Usage:
./sort [-a ALGORITHM] [-f INPUTFILE] [-o OUTPUTFILE] [-h] [-d] [-p] [-t] [-c]
Example:
./sort -h
./sort -a S -f input.txt -o output.txt -d -t -c -p
./sort -a I -t -c
./sort
Options:
-a ALGORITHM: Use ALGORITHM to sort.
ALGORITHM is a single character representing an algorithm:
S for selection sort
B for bubble sort
I for insertion sort
H for shell sort
R for radix sort
-f INPUTFILE: Obtain integers from INPUTFILE instead of STDIN
-o OUTPUTFILE: Place output data into OUTPUTFILE instead of STDOUT
-h: Display this help and exit
-d: Display input: unsorted integer sequence
-p: Display output: sorted integer sequence
-t: Display running time of the chosen algorithm in milliseconds
-c: Display number of comparisons (excluding radix sort)
3. Format of the input data. The first line of the input contains a number n which is the number of integers
to sort. Subsequent n numbers are written one per line which are the numbers to sort. Here is an example
of input data:
5 // this is the number of lines below = number of integers to sort
7
-8
4
0
-2
4. Format of the output data. The sorted integers are printed one per line in increasing order. Here is the
output corresponding to the above input:
-8
-2
0
4
7
5. (50 points) Your tasks include implementing the following five sorting algorithms in corresponding cpp
files.
(a) selection sort in selection-sort.cpp
(b) insertion sort in insertion-sort.cpp
(c) bubble sort in bubble-sort.cpp
(d) shell sort in shell-sort.cpp
(e) radix sort in radix-sort.cpp
i. Implement the radix sort algorithm that can sort 0 to (2
16 −1) but takes input −2
15 to (2
15 −1) .
ii. About radix sort of negative numbers: “You can shift input to all positive numbers by adding a
number which makes the smallest negative number zero. Apply radix sort and next make a reverse
shift to get the initial input.”
3
6. (20 points) Generate the sets of the sizes 102
, 103
, 104
, and 105
integers in three different orders.
(a) random order
(b) increasing order
(c) decreasing order
HINT: The standard library <cstdlib provides functions srand() and rand() to generate random
numbers.
7. Measure the average number of comparisons (excluding radix sort) and average running times of each
algorithms on the 12 integer sequences.
(a) (20 points) Insert additional code into each sort (excluding radix sort) to count the number of comparisons performed on input integers. The following tips should help you with determining how many
comparisons are performed.
i. You will measure 3 times for each algorithm on each sequence and take average
ii. Insert the code that increases number of comparison num_cmps++typically in an if or a loop
statement
iii. Remember that C++ uses the shortcut rule for evaluating boolean expressions. A way to count
comparisons accurately is to use comma expressions. For instance
while (i < n && (num_cmps++, a[i] < b))
HINT: If you modify sort.cpp and run several sorting algorithms subsequently, you have to call
resetNumCmps() to reset number of comparisons between every two calls tos-sort() .
(b) Modify the code in sort.cpp so that it repeatedly measures the running time of s-sort() .
i. You will measure roughly 107
times for each algorithm on each sequence and take the average.
You have to run for the same number of rounds for each algorithm on each sequence, and make
sure that each result is not 0.
ii. When you measure the running time of sorting algorithms, please reuse the input array but fill
with different numbers. Do not allocate a new array every time, that will dramatically slower the
program.
iii. To time a certain part of the program, you may use functions clock() defined in header file
<ctime, or gettimeofday() defined in <sys/time.h. Here are the examples of how to use
these functions. The timing part is also completed in the template programs. However, you will
apply these function to future assignments.
The example using clock() in <ctime:
#include <ctime
...
clock_t t1, t2;
t1 = clock(); // start timing
...
/* operations you want to measure the running time */
...
t2 = clock(); // end of timing
double diff = (double)(t2 - t1)/CLOCKS_PER_SEC;
cout < < "The timing is " < < diff < < “ ms” < < endl;
The example using gettimeofday()in <sys/time.h:
#include <sys/time.h
...
struct timeval start, end;
...
gettimeofday(&start,0); // start timing
...
/* operations you want to measure the running time */
...
4
• Report (110 points)
Write a report that includes all following elements in your report.
1. (5 points) A brief description of assignment purpose, assignment description, how to run your programs,
what to input and output.
The purpose of this assignment was to gain a better understanding of the relative efficiency of different
sorting algorithms on a variety of input types, both in terms of number of comparisons and time taken. We
are assigned to implement various sorting algorithms and experimentally observe their running times.We
are supposed to implement 5 sorting algorithms: selection sort, insertion sort, bubble sort, shell sort, and
radix sort. The program is run by the command ./sort [-a] [-f] [-o] [-h] [-d] [-p] [-t] [-c]. The command
line arguments correspond to the desired algorithm, input file, output file, whether or not the user wants to
display the help, display input, display output, display running time in milliseconds, and display number
of comparisons, excluding radix sort because radix sort is a non-comparison-based sorting algorithm. The
user should have the data in an input file, specified in the command line arguments passed to the main
function in the program. Further, we learned the basic use of git and GitHub, as well as some experience
in programming as part of a group.
2. (5 points) Explanation of splitting the program into classes and a description of C++ object oriented
features or generic programming used in this assignment.
We split the program into classes so that we could have a general virtual ’sort’ class which could later be
cast to one of a number of child classes. This allowed us to handle each preference of sorting type
separately while allowing a common interface for the user. Generic programming features are the general
algorithms executed by the various classes, as these are implementable in a similar fashion regardless of
language. Object-oriented features include the use of a virtual class which is later cast to a child based
upon command line inputs.
3. (5 points) Algorithms. Briefly describe the features of each of the five sorting algorithms.
Radix Sort- Radix sort uses a series of counting sorts from the least significant to the most significant
places on a value, necessitating a stable counting sort algorithm, and taking in values up signed integers
between (−2
15)and (2
15 −1). It is capable of sorting negative numbers by supplying an offset to make
all values positive, and then returning them to their original values with a commensurate negative offset
at the end of the process. This particular implementation of radix sort utilizes a byte-level counting sort,
which then conducts itself in the usual manner of counting sorts by using three arrays, scanning for indices,
cascading addition in the vocabulary array, and then using inverted index referencing to determining the
value and number of array cells to be filled. It can sort in linear time with the given constraints of data.
Shell Sort- Shell sort uses a technique of segmenting normally distributed data across an interval into equal
sub-intervals. The allocated into the correct sub-interval, and is sorted using insertion sort. Afterwards, the
sub-intervals are stitched together, resulting in a sorted list. Because the sub-intervals allocation allows an
insertion sort operation to be nearly sorted already, it can approach constant time given normally distributed
data, and the other operations are linear.
Bubble Sort- Bubble combs linearly from the first element in the array to the last element of interest,
taking up the largest element that it finds and comparing it to its upper neighbor. After each iteration, it
becomes uninterested in the next highest element of interest in the array, thereafter restricting its search to
those elements that it considers unsorted. In this way it will always handle data in at least O(n
2
) time.
Insertion Sort- Insertion sort, similarly to Bubble sort, combs linearly through the array. However, instead
of carrying the largest element to the top, it instead will compare each element to its neighbors and carry
small elements to the bottom. An element x at [a] will be compared to its neighbor y at [a+1]: if it is
larger, then it will switch their indices. Then, y at [a] will be compared to the element at [a - 1] . This will
continue until all elements are sorted, and it runs also in O(n
2
) time.
Selection Sort- Selection sort will go through the element from smallest element to largest, and on each
iteration compare the first element to every other in the list. If it finds that another element is smaller, then
it will place that one at the front of the list. This algorithm has both a best and worst case of n2
time, and is
horribly inefficient.
4. (20 points) Theoretical Analysis. Theoretically analyze the time complexity of the sorting algorithms
with input integers in decreasing, random and increasing orders and fill the second table. Fill in the first
table with the time complexity of the sorting algorithms when inputting the best case, average case and
5
worst case. Some of the input orders are exactly the best case, average case and worst case of the sorting
algorithms. State what input orders correspond to which cases. You should use big-O asymptotic notation
when writing the time complexity (running time).
Complexity best average worst
Selection Sort O(n
2
) O(n
2
) O(n
2
)
Insertion Sort O(n) O(n
2
) O(n
2
)
Bubble Sort O(n) O(n
2
) O(n
2
)
Shell Sort O(n log n) O(n(log n))2
) O(n(log n))2
)
Radix Sort O(n) O(n) O(n) or O(k)
Complexity inc ran dec
Selection Sort O(n
2
) O(n
2
) O(n
2
)
Insertion Sort O(n) O(n
2
) O(n
2
)
Bubble Sort O(n) O(n
2
) O(n
2
)
Shell Sort O(n log n) O(n(log n))2
) O(n(log n))2
)
Radix Sort O(n) O(n) or O(k) O(n) or O(k)
inc: increasing order; dec: decreasing order; ran: random order
5. (65 points) Experiments.
(a) Briefly describe the experiments. Present the experimental running times (RT) and number of comparisons (#COMP) performed on input data using the following tables.
For the experiments, we created lists of incrementing, random and decrementing values. We extensively tested each algorithm and took an average of the run times. This rigorous testing led us to the
following results:
RT Selection Sort (ms) Insertion Sort (ms) Bubble Sort (ms)
n inc ran dec inc ran dec inc ran dec
100 0.043 0.052 0.046 0.003 0.031 0.05 0.003 0.098 0.078
103 3.34 3.51 3.44 0.012 2.23 4.47 0.011 7.21 7.67
104 175 196 279 0.134 143 235 0.092 375 329
105 19332 21780 32388 0.713 11359 23823 0.598 44540 49056
RT Shell Sort (ms) Radix Sort (ms)
n inc ran dec inc ran dec
100 0.007 0.028 0.12 0.062 0.056 0.049
103 0.107 0.428 0.185 0.33 0.328 0.404
104 1.143 4.88 2.16 2.28 1.09 1.91
105 10.205 55.9 19 20.43 20.56 20
#COMP Selection Sort Insertion Sort
n inc ran dec ran inc dec
100 4950 4950 4950 2608 99 5049
103 499500 499500 499500 250035 999 500499
104 49995000 49995000 49995000 25222691 9999 49994956
105 4999950000 4999950000 4999950000 2506169125 99999 4999950203
#COMP Bubble Sort Shell Sort
n ran inc dec ran inc dec
100 4929 99 4950 902 503 668
103 499490 999 499500 15683 8006 11716
104 49991084 9999 49994999 258010 120005 169245
105 4999508670 99999 4999950000 4259397 1500006 2196626
inc: increasing order; dec: decreasing order; ran: random order
As we can see, the run time and number of comparisons do increase with number of elements on the list.
The values for the number of comparison match the intended Big O notation.
6
(a) For each of the five sort algorithms, graph the running times over the three input cases (inc, ran, dec)
versus the input sizes (n); and for each of the first four algorithms graph the numbers of comparisons
versus the input sizes, totaling in 9 graphs.
i. All of these graphs have been plotted in Log base 10 on both values.
7
8
9
HINT: To get a better view of the plots, use logarithmic scales for both x and y axes.
Just to clarify, the last graph (Shell Sort) should be (Comparisons) on the y-axis.
(a) To compare performance of the sorting algorithms you need to have another 3 graphs to plot the results
of all sorts for the running times for each of the input cases (inc, ran, dec) separately.
10
HINT: To get a better view of the plots, use logarithmic scales for both x and y axes.
1. (5 points) Discussion. Comment on how the experimental results relate to the theoretical analysis and explain
any discrepancies you note. Is your computational results match the theoretical analysis you learned from
class or textbook? Justify your answer. Also compare radix sort’s running time with the running time of four
comparison-based algorithms.
We can see a correlation for between the theoretical and experimental results. For Selection Sort we notice that
the BigO asymptotic function is n 2
. From our results we can see that we have 4950 comparisons done on to
sort our algorithm in all three cases. Even though this seems like only half of the time our comparisons will be
done, we know from mathematics that the BigO function must be asymptotically larger than our function, so
our experimental value agrees with our results. Another algorithm we can analyze would be Bubble Sort. From
the theoretical predictions we see that the BigO should be a case of O(n) for increasing lists and a O(n
2
) for
the average and worst case. Our experimental results do follow this mathematical correlation with the best case
being a run time of 0.598ms for the 105
inputs and 44540 and 49056 for the average and worst case.
The Radix Runt Time is significantly lower than the three comparison based algorithms but similar to the Shell
Sort run times. For the average case, we do see that the Radix perform better than the Shell.
2. (5 points) Conclusions. Give your observations and conclusion. For instance, which sorting algorithm seems to
perform better on which case? Do the experimental results agree with the theoretical analysis you learned from
class or textbook? What factors can affect your experimental results?
For the case of small input size (10 2
and 103
), the Shell Sort and Radix Sort seems to be the best algorithms
for the least number of comparisons. The Shell Sort performs at a run time of milliseconds for small input
11
sizes and the Radix sort performs on the millisecond range also. This agrees with our analysis of the BigO for
OO(n2
(logn)) for the average and worst cases for Shell Sort and O(n) for all the cases in Radix sort. When we
begin to use larger data sets (10 4
and 105
), we see that the Radix Sort has the smallest values in Run Time
for our inputs. This agrees with our theoretical analysis that states the worst case should be O(n). The factors
that could be affecting our experimental results could be the fact that our Radix Sort was implemented with
operations on the byte level, and so would be faster to compute than other arithmetic operations regardless of the
inherent efficiency of the algorithm. Other factors could be varied computational load on the servers at the times
that these algorithms were tested, or even the uncertainty that identical processors are handling our algorithms,
given that the server is something of a black box. One last factor could be the fact that we ran most of the
comparisons on a laptop and not TAMU’s Unix servers. These discrepaciencs gave us different runtimes due to
the hardware integrated into the seperate machines.
12