Programming Assignment -- You are asked to implement the insertion sort, m erge sort and quick sort algorithms for an array of integers and then perform the measurements as detailed below.
1.For each algorithm, implement the functions that take an array of integers and the size of the array and then sort it in ascending order. Add counters to count the number of key comparisons and the number of data moves during sorting.
2.For the quick sort algorithm, you are supposed to take the first element of the array as the pivot.
3.Write a main function to measure the time required by each sorting algorithm. To this end, use the library function clock(), which is defined in time.h. Invoke the clock() library function before and after each sorting algorithm to measure the elapsed time in milliseconds.
4.Although you will write your own main function to get the experimental results, we will also write our own main function to test whether or not your algorithms work correctly. In our main function, we will call your sorting algorithms with the following prototypes.
void insertionSort( int* arr, const int size, int& compCount, int& moveCount );
void mergeSort( int* arr, const int size, int& compCount, int& moveCount );
void quickSort( int* arr, const int size, int& compCount, int& moveCount );
In all of these prototypes, arr is the array that the algorithm will sort, size is the array size, compCount is the number of key comparisons in sorting, and moveCount is the number of data moves in sorting. After returning this function, arr should become sorted.
For counting key comparisons, you should count each comparison like "a < b" as 1 comparison. For counting number of moves, you should count each assignment as 1 move, for example, swap method has three moves:
void swap( DataType& x, DataType& y ) {
DataType temp = x; x = y;
y = temp;
}
5.Put the implementations of these functions in sorting.cpp, and their interfaces in sorting.h. Do not include your main function in these files. Submit your main function inside a separate file, called main.cpp.
6.You will lose a significant amount of points if you do not comply with these naming conventions. After implementing the sorting algorithms,
1.Create three identical arrays with random 20,000 integers using the random number generator function rand. Use one of the arrays for the insertion sort, another one for the merge sort, and the last one for the quick sort algorithm. Output the number of key comparisons, the number of data moves, and the elapsed time to sort these integers using each of these algorithms. Repeat this experiment for at least 5 different input sizes that are greater than 20,000 (for instance, 20 000, 40 000, 60 000, 80 000, 100 000). With the help of a graphical plotting tool, present your experimental results graphically. Note that you should plot the number of key comparisons, the number of data moves, and the elapsed time in different figures.
2.Then, create three identical copies of an array with 20,000 integers that are sorted in descending order. Use each array for each algorithm. Repeat all of the experiments and present your experimental results graphically. (That is, for each algorithm, create arrays with at least 5 different input sizes and output the number of key comparisons, the number of data moves, and the elapsed time to sort these arrays and present your results graphically.)
3.Lastly, create three identical copies of an array with 20,000 integers that are sorted in ascending order. Use each array for each algorithm. Repeat all of the experiments and present your experimental results graphically.
Interpret your experimental results that you obtained in Question 3. Compare these results with the theoretical ones for each sorting algorithm. Explain any differences between the experimental and theoretical results.