Q2:

a) Write code in your main function that performs the following: a)For each n {10^3, 5x10^3, 10^4, 5x10^4, 10^5}, randomly generate five integer arrays of length n.

b)Run each of the five comparison sorts you implemented in Step 1 on all the five arrays generated in Step 2(a) and record the worst-case actual running time and number of comparisons performed among elements in the input array.

Use the following code:

#include #include

using namespace std;

void displayArray(int a[], int n) { cout << " Array after sorting: " << endl; for (int i = 0; i < n; i++) cout << a[i] << "\t"; cout << endl; }

void selectionSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int minimum = i;

for (int j = i + 1; j < n; j++) //find the minimum element if (a[minimum] > a[j]) minimum = j;

int temp = a[minimum]; // swap with the ith location element a[minimum] = a[i]; a[i] = temp; } displayArray(a, n); }

void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { //sorted sub-array int min = a[i]; int j = i - 1;

while (j >= 0 && a[j] > min) { // find minimum from unsorted sub-array a[j + 1] = a[j]; //shifting --j; } } displayArray(a, n); }

void shellSort(int a[], int n) { int k = floor(log2(n)); //calculate k int gap = pow(2, k) - 1; //initialize gap

while (gap >= 1) { for (int i = gap; i < n; i++) { int temp = a[i]; int j; for (j = i; j >= gap && a[j - gap] > temp; j -= gap) //jump the gap and swap if small a[j] = a[j - gap]; a[j] = temp; } k--; gap = pow(2, k) - 1; //decrement gap } displayArray(a, n); }

void swap(int* a, int* b) { //swapping function int t = *a; *a = *b; *b = t; }

int partition(int a[], int low, int high) { //partition function int pivot = a[high]; int i = (low - 1);

for (int j = low; j <= high - 1; j++) { //find pivot element from low-> high if (a[j] < pivot) { i++; swap(&a[i], &a[j]); } } swap(&a[i + 1], &a[high]); return (i + 1); }

void quickSort(int a[], int low, int high) { if (low < high) { int pi = partition(a, low, high); quickSort(a, low, pi - 1); quickSort(a, pi + 1, high); }

}

void merge(int a[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++) L[i] = a[l + i];

for (j = 0; j < n2; j++) R[j] = a[m + 1 + j];

i = 0; j = 0; k = l;

while (i < n1 && j < n2) { if (L[i] <= R[j]) { a[k] = L[i]; i++; } else { a[k] = R[j]; j++; } k++; }

while (i < n1) { a[k] = L[i]; i++; k++; }

while (j < n2) { a[k] = R[j]; j++; k++; } }

void mergeSort(int a[], int l, int r) { if (l < r) { int m = l + (r - l) / 2;

mergeSort(a, l, m); mergeSort(a, m + 1, r);

merge(a, l, m, r); } }

int main() { int n; cout << "Enter the total number of elements: "; cin >> n;

int a[n]; cout << "Enter the elements:" << endl; for (int i = 0; i < n; i++) cin >> a[i];

cout << "Select the sorting algorith: " << endl; cout << "1.Selection sort" << endl; cout << "2.Insertion sort" << endl; cout << "3.Shell sort" << endl; cout << "4.Quick sort" << endl; cout << "5.Merge sort" << endl;

int choice = 0; cout << "Enter choice: "; cin >> choice;

switch (choice) { case 1: selectionSort(a, n); break; case 2: insertionSort(a, n); break; case 3: shellSort(a, n); break; case 4: quickSort(a, 0, n - 1); displayArray(a, n); break; case 5: mergeSort(a, 0, n - 1); displayArray(a, n); break; default: cout << "Invalid Choice" << endl; } return 0; }