SortHelper.h :

#pragma once #include #include #include #include

using namespace std;

namespace SortHelper { /*generate an array of n integers and every integer is in the range [rangeL, rangeR] */ int* generateRandomArray(int n, int min, int max) { int *arr = new int[n]; srand(time(NULL)); for (int i = 0; i void printArray(T arr[], int n) { for (int i = 0; i bool isSorted(T arr[], int n) { for (int i = 0; i arr[i + 1]) { cout void timing(string sortAlgorithm, void(*Sort)(T[], int), T arr[], int n) { clock_t startTime = clock(); Sort(arr, n); clock_t endTime = clock(); assert(isSorted(arr, n)); cout

main.cpp:

#include #include #include "SortHelper.h" using namespace std;

/*To fill merge function to merge sorted sublists arr[l, l+1, ..., mid] and arr[mid+1, mid+1, ..., r] such that arr[] is sorted at the end.*/ template void merge(T arr[], int L, int mid, int R) { }

template void _mergeSort(T arr[], int L, int R) { if (L >= R) return; int mid = (L + R) / 2; _mergeSort(arr, L, mid); _mergeSort(arr, mid + 1, R); merge(arr, L, mid, R); }

template void mergeSort(T arr[], int n) { _mergeSort(arr, 0, n - 1); }

/*To fill the partition function: pick arr[L] as the pivot and reorder arr[] such that all numbers before pivot in arr[] are smaller and all other behind it are larger. return the index of pivot after partition. */ template int partition(T arr[], int L, int R) {

}

//Apply quick sort on the subarray arr[l, l+1, ..., r-1, r] of arr[] template void _quickSort(T arr[], int L, int R) { if (L >= R) return; int pivot = partition(arr, L, R); _quickSort(arr, L, pivot - 1); _quickSort(arr, pivot + 1, R); }

template void quickSort(T arr[], int n) { _quickSort(arr, 0, n - 1); }

/*To fill count sort function it applies counting sort on arr[] according to the d-th digit;*/ template void countSort(T arr[], int n, int d) { }

/*o fill radix sort function. Apply radix sort sorts arr[] of size n*/ template void radixSort(T arr[], int n) { }

int main() { int n = 10000; if (n==0) { cout 1 Introduction In this homework, you will implement three sorting algorithms, and then test their efficiency (running time). This assignment will consist of not only coding, but also testing your code on large data set. The three sorting algorithms to implement are Merge Sort, Quick Sort and Radix Sort. Note that to realize Radix Sort, a function of counting Sort by digits is needed to be implemented firstly. 2 Instructions The following files have been given to you: 1. A C++ header file (SortHelper.h) declaring a namespace SortHelper of functions. 2. A C++ source file (main.cpp containing a main function with tests. Download the files on blackboard. In Sort Helper.h, there are several functions which are creating a data set of the given size, measuring the running time of any given function in milliseconds, checking whether the array is sorted, etc. In main.cpp, you need to implement the three sorting algorithms and test the efficiency of each sorting function. Please read the instruction in the main.cpp carefully. Efficiency Test: After you have correctly implemented the sorting algorithms, executing the main func- tion, you will see how long each sorting function takes to run on both random and sorted inputs. Please test each algorithm on both random and sorted input of different sizes: 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000. You will get a list of running time in milliseconds. (The timing() function in Sort Helper is to test the speed of an given function.) 3 What to submit You need to submit the following files via blackborad. 1. A C++ source file (main.cpp containing a main function with tests. 2. A pdf file contains a table of running times for three algorithms on random and sorted arrays of sizes 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000, and two charts to statistic the efficiency. The first chart is for running times of three algorithms on random arrays of the above different sizes, while the second chart is for sorted arrays. In addition, your observation, discussion and comments about the efficiency should be included. 1 Introduction In this homework, you will implement three sorting algorithms, and then test their efficiency (running time). This assignment will consist of not only coding, but also testing your code on large data set. The three sorting algorithms to implement are Merge Sort, Quick Sort and Radix Sort. Note that to realize Radix Sort, a function of counting Sort by digits is needed to be implemented firstly. 2 Instructions The following files have been given to you: 1. A C++ header file (SortHelper.h) declaring a namespace SortHelper of functions. 2. A C++ source file (main.cpp containing a main function with tests. Download the files on blackboard. In Sort Helper.h, there are several functions which are creating a data set of the given size, measuring the running time of any given function in milliseconds, checking whether the array is sorted, etc. In main.cpp, you need to implement the three sorting algorithms and test the efficiency of each sorting function. Please read the instruction in the main.cpp carefully. Efficiency Test: After you have correctly implemented the sorting algorithms, executing the main func- tion, you will see how long each sorting function takes to run on both random and sorted inputs. Please test each algorithm on both random and sorted input of different sizes: 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000. You will get a list of running time in milliseconds. (The timing() function in Sort Helper is to test the speed of an given function.) 3 What to submit You need to submit the following files via blackborad. 1. A C++ source file (main.cpp containing a main function with tests. 2. A pdf file contains a table of running times for three algorithms on random and sorted arrays of sizes 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000, and two charts to statistic the efficiency. The first chart is for running times of three algorithms on random arrays of the above different sizes, while the second chart is for sorted arrays. In addition, your observation, discussion and comments about the efficiency should be included