Description
Question 1 – 25 points
Trace the following sorting algorithms to sort the array [ 6, 1, 5, 3, 7, 2, 8, 4 ] in ascending order. Use
the array implementation of the algorithms as described in the textbook and show all major steps.
Selection sort
Insertion sort
Bubble sort
Merge sort (also list the calls to mergesort and merge functions in the order they occur)
Quick sort (also list the calls to quicksort and partition functions in the order they
occur; assume that the first item is chosen as the pivot)
Question 2 – 60 points
Implement the following functions in the sorting.cpp file:
(a) [30 points] Implement the insertion sort, merge sort, and quick sort algorithms. Your
functions should take an array of integers and the size of that array and then sort it in
descending order. Add two counters to count and return the number of key comparisons and
the number of data moves for all sorting algorithms. For the quick sort algorithm, you are
supposed to take the first element of the array as pivot. Your functions should have the
following prototypes (all prototypes should be in sorting.h):
void insertionSort(int* arr, const int size, int& countComp, int& countMove);
void mergeSort(int* arr, const int size, int& countComp, int& countMove);
void quickSort(int* arr, const int size, int& countComp, int& countMove);
For key comparisons, you should count each comparison like k1 < k2 as one comparison,
where k1 and k2 correspond to the value of an array entry (that is, they are either an array
entry like arr[i] or a local variable that temporarily keeps the value of an array entry).
For data moves, you should count each assignment as one move, where either the right-hand
side of this assignment or its left-hand side or both of its sides correspond to the value of an
array entry (e.g., a swap function has three data moves).
(b) [15 points] To test your implementation and conduct the experiments described below, you
must write additional auxiliary global functions as follows. The prototypes of these functions
are given below. They create three identical arrays that will be used for testing the sorting
algorithms with random numbers (generated using the random number generator function
rand), numbers in ascending order, and numbers in descending order, respectively.
void createRandomArrays(int*& arr1, int*& arr2, int*& arr3, const int size);
void createAscendingArrays(int*& arr1, int*& arr2, int*& arr3, const int size);
void createDescendingArrays(int*& arr1, int*& arr2, int*& arr3, const int size);
(c) [15 points] In this part, you will analyze the performance of the sorting algorithms that you
implement. Call the auxiliary global functions given above to create the arrays with different
contents. For each scenario (random, ascending, descending), use the following sizes for the
arrays: 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000. Run each of the sorting
algorithms with each scenario and output the elapsed time in milliseconds, the number of
key comparisons and the number of data moves. Your program should produce an output
similar to the one given below. Include this output to the answer of Question 2 in the pdf
submission. Also add a screenshot of the console output (on dijkstra) to the solution of
Question 2 in the pdf file.
Together with your code, provide a basic Makefile which compiles all of your code and
creates an executable file named hw1. Check out this tutorial for writing a simple makefile:
http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/
Please make sure that your Makefile works properly, otherwise you will not get any
points from Question 2.
Question 3 – 15 points
After running your programs, prepare a single page report about the experimental results that you
obtain in Question 2. With the help of a spreadsheet program (Microsoft Excel, Matlab or other
tools), plot elapsed time versus the array size for each sorting algorithm implemented in Question 2.
Combine the outputs of each sorting algorithm in a single graph.
In your report, interpret and compare your empirical results with the theoretical ones. Explain any
differences between the empirical and theoretical results, if any.
Do not forget to discuss how the time complexity of your program changed when you applied the
sorting algorithms to already sorted arrays (ascending and descending) instead of an array containing
randomly generated numbers. Also briefly explain the rationality behind this change.
————————————————————-
Analysis of Insertion Sort
Array Size Time Elapsed countComp countMove
5000 x ms x x
10000 x ms x x
…
————————————————————-
Analysis of Merge Sort
Array Size Time Elapsed countComp countMove
5000 x ms x x
10000 x ms x x
…
————————————————————-
Analysis of Quick Sort
Array Size Time Elapsed countComp countMove
5000 x ms x x
10000 x ms x x
…
