//Output the list in a 100data.txt file. Read the integers from the file in an array or linked list//

#include #include #include

// helper function for quick sort int partition(int arr[], int l, int h) { int pivot = arr[h]; int i = (l - 1); //smaller element index

// iterate for array from l to h for (int j = l; j <= h - 1; j++) { // current element smaller than pivot if (arr[j] < pivot) { i++; // swap elements int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } // swap i+1 and h array index elements int t = arr[i + 1]; arr[i + 1] = arr[h]; arr[h] = t; return (i + 1); } // defination for quicksort function void quickSort(int arr[], int l, int h) { // for left and right index not equal if (l < h) { //pi is partitioning index int pi = partition(arr, l, h);

// recursively iterate till array sorted // divide array into two, sort them seperatly quickSort(arr, l, pi - 1); quickSort(arr, pi + 1, h); } }

// for merge sort, helper merge void merge(int arr[], int l, int m, int r) { // declare required variables int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2];

// copy from L to R for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

// merge temp values back to array i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; }

// remaining elements of L[] while (i < n1) { arr[k] = L[i]; i++; k++; }

// copy the remaining elements of R[] while (j < n2) { arr[k] = R[j]; j++; k++; } }

// Actual merge sort function void mergeSort(int arr[], int l, int r) { // for left index less than right if (l < r) { // middle index m int m = l + (r - l) / 2;

// Divide into two parts mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // merge both parts merge(arr, l, m, r); } }

// Driver program int main(void) { // Use 191022310 as seed for random generator srand(191022310); int i; // Here i am initializing 300 as size. You can change if you want. int size = 300; int arr[size]; for (int i = 0; i < size; i++) { // initializing the array value with unique random integer arr[i] = rand(); //printing the num printf("%d ", arr[i]); } // ABOVE GIVEN CODE NOT CHANGED

// so that merge sort should not get same arr int *array_for_quicksort = arr; // test, implementation sort arr using quicksort clock_t t; t = clock(); // before time quickSort(array_for_quicksort, 0, size - 1); t = clock() - t; //after time double time_taken = ((double)t) / CLOCKS_PER_SEC;

// EXECUTION TIME for quick sort printf("time taken by quick sort : %f secs ", time_taken );

// sort arr using merge sort clock_t t1; t1 = clock(); mergeSort(arr, 0, size - 1); t1 = clock() - t1; double time_taken1 = ((double)t1) / CLOCKS_PER_SEC;

// EXECUTION TIME for merge sorts printf("time taken by mergeSort: %f secs ", time_taken1 );

return 0; }

//Output the list in a 100data.txt or 100data.csv file. Read the integers from the file in an array or linked list//