'''Source Code:'''
#include <iostream>#include <cstdlib>#include <cstring>#include <vector> //Generates random numbers and assigns them to the arrayvoid fillArray(int* arr, int size) { for (int i = 0; i < size; i++) { arr[i] = rand() % size; }} //Performs Bubble Sort on the array passed through parametervoid bubbleSort(int *arr, int size) { for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } }} //Performs Selection Sort on the array passed through parametervoid selectionSort(int *arr, int size) { for (int i = 0; i < size; i++) { int minIdx = i; for (int j = i; j < size; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } //swap int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; }} //Performs Insertion Sort on the array passed through parametervoid insertionSort(int *arr, int size) { for (int i = 0; i < size; i++) { int curr = arr[i]; int j = i; for (j = i; j > 0 && arr[j - 1] > curr; j--) { arr[j] = arr[j - 1]; } arr[j] = curr; }} void heapify(int *arr, int n, int i){ int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { std::swap(arr[i], arr[largest]); // Recursively heapify the affected sub-tree heapify(arr, n, largest); }} //Performs Heap Sort on the array passed through parameter//Acts as a wrapper functionvoid heapSort(int *arr, int size) { // Build heap (rearrange array) for (int i = size / 2 - 1; i >= 0; i--) heapify(arr, size, i); // One by one extract an element from heap for (int i = size - 1; i >= 0; i--) { // Move current root to end stdFile::swap(arr[0], arr[i]); // call max heapify on the reduced heap heapify(arr, i, 0); }} //Performs Quick Sort on the array passed through parametervoid quickSort(int *arr, int left, int right) { int leftIdx = left, rightIdx = right; int tmp; int pivot = arr[(left + right) / 2]; /* partition */ while (leftIdx <= rightIdx) { while (arr[leftIdx] < pivot) leftIdx++; while (arr[rightIdx] > pivot) rightIdx--; if (leftIdx <= rightIdx) { tmp = arr[leftIdx]; arr[leftIdx] = arr[rightIdx]; arr[rightIdx] = tmp; leftIdx++; rightIdx--; } }; /* recursion */ if (left < rightIdx) quickSort(arr, left, rightIdx); if (leftIdx < right) quickSort(arr, leftIdx, right);} //Merges the arrays and sorts itvoid merge(int *arr, std::vector<int>& tmp, int start, int start2, int end) { int lptr = start; int rptr = start2; int i = start; while (lptr < start2 && rptr <= end) { if (arr[lptr] < arr[rptr]) tmp[i++] = arr[lptr++]; else tmp[i++] = arr[rptr++]; } while (lptr < start2) { tmp[i++] = arr[lptr++]; } while (rptr <= end) { tmp[i++] = arr[rptr++]; } for (i = start; i <= end; i++) { arr[i] = tmp[i]; }} //this function sorts arr from index start to endvoid mergeIndexSort(int* arr, std::vector<int>& tmp, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeIndexSort(arr, tmp, start, mid); mergeIndexSort(arr, tmp, mid + 1, end); merge(arr, tmp, start, mid + 1, end); }} //Acts as a wrapper functionvoid mergeSort(int* arr, int size) { std::vector<int> tmp(size); //call mergeSort with the array, the temporary //and the starting and ending indices of the array mergeIndexSort(arr, tmp, 0, size - 1);} //Print the values (Not used due to big size of array)void print(int *arr, int size){ for (int i = 0; i < size; i++) { std::cout << arr[i] << " "; } std::cout << std::endl;} int main(int argc, char *argv[]) { //Get the size of the array int n = std::atoi(argv[1]); // Create 6 arrays of size n and allocate memory for them int *bubbleArray = new int[n]; int *selectionArray = new int[n]; int *insertionArray = new int[n]; int *heapArray = new int[n]; int *mergeArray = new int[n]; int *quickArray = new int[n]; //Fill the array with randomly generated numbers fillArray(bubbleArray, n); //print(bubbleArray, n); //COPY the values to the other //This adds consistency among the elements of the array std::memcpy(selectionArray, bubbleArray, n*sizeof(int)); std::memcpy(insertionArray, bubbleArray, n * sizeof(int)); std::memcpy(heapArray, bubbleArray, n * sizeof(int)); std::memcpy(mergeArray, bubbleArray, n * sizeof(int)); std::memcpy(quickArray, bubbleArray, n * sizeof(int)); //Call the sorting algorithms 1 by 1 with their respecive array bubbleSort(bubbleArray, n); std::cout << "Bubble Sort performed." << std::endl; selectionSort(selectionArray, n); std::cout << "Selection Sort performed." << std::endl; insertionSort(insertionArray, n); std::cout << "Insertion Sort performed." << std::endl; heapSort(heapArray, n); std::cout << "Heap Sort performedSortingAlgorithmsM1." << std::endl; mergeSort(mergeArray, n); std::cout << "Merge Sort performedcpp." << std::endl; quickSort(quickArray, 0, n-1); std::cout << "Quick Sort performed." << std::endl; //Deallocate the arrays delete[] bubbleArray; delete[] selectionArray; delete[] insertionArray; delete[txt] heapArray; delete[] mergeArray; delete[] quickArray; return 0;}
0.00 808.26 0.00 8 0.00 10.01 mergeIndexSort(int*, std::vector<int, std::allocator<int> >&, int, int)
0.00 808.26 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z9fillArrayPii
=== Assignment 2 ===
=== Assignment 3 ===