Questions by bjenkins - Page 31
IN C++, Using Notepad ++, Compiled in Developer Command Prompt for VS 2019Implement the quicksort, Shell's sort, and insertion sort algorithms as functions. Recall that the quicksort algorithm needs two functions to work properly.We're going to time how fast the different algorithms can sort under various conditions.Begin by creating 3 integer arrays, all of length 20 elements. Fill these arrays with random numbers, but I want the three arrays to be identical. Recall that if you want a range for a random number, it's rand()%(max+1-min)+min; where min in max specify the range of values you like [min, max] (inclusively). By being identical, the sorting time will be found fairly.Output what the original unsorted array looks like, and then show the sorted list using each sorting algorithm. This is just to ensure that each sort is working correctly.Now we're going to time how long it takes each sort to run given various input patterns. Instead of 20 elements, we're going to now be working with 100,000 elements.Time how long it takes to sort the array for each function using the code below:The way to get the time in milliseconds is:#include clock_t start, end;double milli_time;start = clock();// Perform any operations you like. Be sure it's only the sort and not printing anything out. Best way is to just have the function call here.end = clock();milli_time = 1000.0 * (end - start) / CLOCKS_PER_SEC;Obviously don't print out the super large arrays, but please give clear output as to which sort you're doing and how long it took.Repeat this entire process again where instead of a list of random elements, the list is already in order: 1 2 3 4 5 ...Here's a function to fill an array with random elements, where min and max represent the lower and upper bounds for the random numbers.#include void getRandomArray(int array[], int size){int min = 0, max = 1000000; // or whatever bounds you wishfor(int i = 0; i < size; i++){array[i] = rand()%(max+1 - min) + min;}}CODE I HAVE ALREADY MADEFile Name sort.cpp#include #include #include #include #include using namespace std;// to get an array with random elementsvoid getRandomArray(int array[], int size){int min = 0, max = 1000000;for(int i = 0; i < size; i++)array[i] = rand()%(max+1 - min) + min;}void quick_Sort(int A[], int p, int r){if (p < r){int q = partition(A, p, r);quickSort(A, p, q - 1);quickSort(A, q + 1, r);}}int partition(int A[], int p, int r){int x = A[r];int i = (p - 1);for (int j = p; j 0; incre /= 2){for (int i = incre; i < n; i += 1){int temp = A[i];int j;for (j = i; j >= incre && A[j - incre] > temp; j -= incre)A[j] = A[j - incre];A[j] = temp;}}}// function to perform insertion sortvoid insertion_Sort(int* list, int size){int current, hold, walker;for (current = 1; current < size; current++){hold = list[current];for(walker = current - 1; walker >=0 && hold < list[walker]; walker--){list[walker+1] = list[walker];}list[walker+1] = hold;}}