C++ sorting

You need to fill an array with either one or 3 functions with a) random data b) data in ascending order c) data in descending order

1) Use the algorithm insertion sort provided void insertionSort(int A[], int n);

2) Use the algorithm quick sort provided (i.e. do not modify the code, it is correct) void quickSort(int A[], int n);

3) Use the algorithm merge sort provided void mergeSort(int A[], int W[], int n);

with W as an array of working storage (W has the same length as the array A)1: declare W in the main function. to time all 3 algorithms with arrays of data filled with a) b) and c) data So, in total there are 9 timings per n where n is the size of the array. Choose the values of n appropriately (suggestion, double n each time and start with n = 1000) For each of the 3 sorting methods and each of the 3 data sets, determine if the cost is O(n), O(n log2n) or O(n2) and identify if this is the best case, worst case, or average case of the algorithm. To get an accurate measure for the time for small values of n, you will need to repeat the experiment m times, that is, time how long it takes to sort an array of n values m times and then divide the total time T by m. For example, for n=1000, you may need to repeat the experiment m=100 times so that the total time is at least 1 time unit. For the fast algorithms, you may need to use m=1000 or larger, to get an accurate time T. Your timings should NOT be 0 seconds. Do not use dynamic arrays nor variable length arrays.

note: Leave in the source code the timing commands so that we can run the code and reproduce the timings (and computations) Comment the source code appropriately and modularize as needed. Remember to name the constants. Declare the main array to be sorted (and possibly the original array of random data) and the working array in the main function of the program as static arrays. Do not use dynamic arrays nor variable length arrays.

------------------------------------------------code I have so far---------------------------------------------------------------------

void insertionSort(int A[ ], int n);

void quickSort(int A[ ], int n);

void quickSort(int A[ ], int low, int high);

int partition(int A[ ], int low, int high);

void mergeSort(int A[ ], int W[ ], int n);

void mergeSort(int A[ ], int low, int high, int W[] );

void merge(int A[ ], int lStart, int lEnd, int rStart, int rEnd, int W[ ]);

// ----------------------------------insertion sort -------------------------

void insertionSort(int A[], int n) {

for (int i = 1; i < n; i++) {

int j;

int t = A[i]; // new value

for (j = i-1; j >= 0 && A[j] > t; j--)

A[j+1] = A[j];

A[j+1] = t;

}

}

// ----------------------------------quick sort -------------------------

// choose the first element as pivot like in the textbook by Liang, Listing 19.8

int partition(int A[], int low, int high) {

int pivot = A[low];

while (low < high) {

// gap is now at A[low]

while (low < high && A[high] >= pivot) {

high--;

}

A[low] = A[high];

// gap is now at A[high]

while (low < high && A[low] <= pivot) {

low++;

}

A[high] = A[low];

}

A[low] = pivot;

// return index of the pivot

return low;

}

void quickSort(int A[], int low, int high) {

if (low >= high) { // correct, fixed from class notes

return;

}

if (low + 1 == high) {

if (A[low] > A[high]) {

int tmp = A[low];

A[low] = A[high];

A[high] = tmp;

}

return;

}

int pivotIndex = partition(A, low, high);

quickSort(A, low, pivotIndex - 1);

quickSort(A, pivotIndex + 1, high);

}

void quickSort(int A[], int n) {

quickSort(A, 0, n-1);

}

// ----------------------------------merge sort -------------------------

void mergeSort(int A[], int W[], int n) {

mergeSort(A, 0, n-1, W);

}

void mergeSort(int A[], int low, int high, int W[] ) {

if (high == low) {

return;

}

// split the array in two and recursively do mergeSort

int mid = (low + high)/2;

mergeSort(A, low, mid, W);

mergeSort(A, mid+1, high, W);

merge(A, low, mid, mid+1, high, W);

}

// merge A[rStart],...,A[lEnd] with A[rStart],....,A[rEnd] into

// W which is indexed by k

void merge(int A[], int lStart, int lEnd, int rStart, int rEnd, int W[]) {

int i = lStart;

int j = rStart;

int k = lStart;

while (i <= lEnd && j <= rEnd) {

if (A[i] < A[j]) {

W[k++] = A[i++];

}

else if (A[i] > A[j]) {

W[k++] = A[j++];

}

else {

// both are equal

W[k++] = A[i++];

W[k++] = A[j++];

}

}

// copy the rest of the array that is not empty

while (i <= lEnd) {

W[k++] = A[i++];

}

while (j <= rEnd) {

W[k++] = A[j++];

}

// copy resulting W back into A at the end

for (i = lStart; i <= rEnd; i++) {

A[i] = W[i];

}

}