Anupznk

Merge Quick Sort

Jun 14th, 2021
423
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<ctime>
  3. #include <stdlib.h>
  4. #include<time.h>
  5. #include <chrono>
  6. using namespace std;
  7.  
  8. int numbers[1000006];
  9. int numbers2[1000006];
  10. int leftArr[1000006];
  11. int rightArr[1000006];
  12. double mergeSortTime[100];
  13. double quickSortTime[100];
  14. int count = 0;
  15.  
  16. void merge(int arr[], int left, int mid, int right) {
  17.     int leftArrLen = mid - left + 1;
  18.     int rightArrLen = right - mid;
  19.  
  20.     for (int i = 0; i<leftArrLen; i++) {
  21.         leftArr[i] = arr[left + i];
  22.     }
  23.  
  24.     for (int i = 0; i<rightArrLen; i++) {
  25.         rightArr[i] = arr[mid + i + 1];
  26.     }
  27.  
  28.     int i = 0;
  29.     int j = 0;
  30.     int k = left;
  31.  
  32.     while (i < leftArrLen && j < rightArrLen) {
  33.         if (leftArr[i] <= rightArr[j]) {
  34.             arr[k] = leftArr[i];
  35.             i++;
  36.             k++;
  37.         } else {
  38.             arr[k] = rightArr[j];
  39.             j++;
  40.             k++;
  41.         }
  42.     }
  43.  
  44.     while(i < leftArrLen) {
  45.         arr[k] = leftArr[i];
  46.         i++;
  47.         k++;
  48.     }
  49.  
  50.     while(j < rightArrLen) {
  51.         arr[k] = rightArr[j];
  52.         j++;
  53.         k++;
  54.     }
  55. }
  56.  
  57. void mergeSort(int arr[], int left, int right) {
  58.     if (left >= right) {
  59.         return;
  60.     }
  61.     int mid = (left + right) / 2;
  62.     mergeSort(arr, left, mid);
  63.     mergeSort(arr, mid+1, right);
  64.     merge(arr, left, mid, right);
  65. }
  66.  
  67. void printSorted(int arr1[], int arr2[], int n) {
  68.     cout << "Merge Sort\tQuick Sort" << endl;
  69.     cout << "----------\t----------" << endl;
  70.     for (int i = 0; i<n; i++) {
  71.         cout << arr1[i] << "\t\t";
  72.         cout << arr2[i];
  73.         cout << endl;
  74.     }
  75. }
  76.  
  77. void swapNums(int &a, int &b){
  78.     int temp;
  79.     temp = a;
  80.     a = b;
  81.     b = temp;
  82. }
  83.  
  84. int partition (int arr[], int left, int right) {
  85.     int pivot = arr[right];     // taking the last element of the sub array as pivot
  86.     int i = left - 1;
  87.     int j;
  88.     for (j = left; j<right; j++) {
  89.         if (pivot > arr[j]){    // if pivot > current element, we need to bring the current element,
  90.                                 // which is smaller than pivot, to the left of the pivot
  91.  
  92.             i++;                // i leads to the place where the pivot needs to sit after
  93.                                 // shifting all the elements that are smaller than the pivot to the left of the pivot
  94.             swapNums(arr[i], arr[j]);
  95.         }
  96.     }
  97.     swapNums(arr[right], arr[i+1]);
  98.     return i + 1;
  99. }
  100.  
  101. int partition_random(int arr[], int left, int right){
  102.     srand(time(0));
  103.     int random = left + rand() % (right - left);
  104.  
  105.     swap(arr[random], arr[right]);
  106.  
  107.     return partition(arr, left, right);
  108. }
  109.  
  110. void quickSort(int arr[], int left, int right) {
  111.     if (left < right) {
  112.         int q = partition(arr, left, right);    // element of q is in the right place
  113.  
  114.         quickSort(arr, left, q-1);
  115.         quickSort(arr, q+1, right);
  116.     }
  117. }
  118.  
  119. void applySort(int arr1[], int arr2[], int n) {
  120.  
  121.     clock_t start_time = clock();
  122.     mergeSort(arr1, 0, n - 1);
  123.     mergeSortTime[count] = float(clock() - start_time) / CLOCKS_PER_SEC;
  124.     cout << "time for merge sort " << mergeSortTime[count] << " seconds\n";
  125.  
  126.     start_time = clock();
  127.     quickSort(arr2, 0, n - 1);
  128.     quickSortTime[count] = float(clock() - start_time) / CLOCKS_PER_SEC;
  129.     cout << "time for quick sort " << quickSortTime[count] << " seconds\n";
  130.  
  131.     count++;
  132.  
  133.     printSorted(arr1, arr2, n);
  134. }
  135.  
  136. int main(){
  137.     string input;
  138.  
  139.     while (true) {
  140.         cout << "\n\nPress 1 to run the algorithm" << endl;
  141.         cout << "Press Q to quit." << endl;
  142.         cin >> input;
  143.         if (input == "Q" || input=="q") {
  144.             cout << "Quitting..." << endl;
  145.             break;
  146.         }
  147.         if (input != "1")
  148.             continue;
  149.  
  150.         cout << "Enter the number of integers" << endl;
  151.         int n;
  152.         cin >> n;
  153.  
  154.         cout << "Enter your choice" << endl;
  155.         cout << "1. Ascending order" << endl;
  156.         cout << "2. Descending order" << endl;
  157.         cout << "3. Random order" << endl;
  158.  
  159.         char order;
  160.         cin >> order;
  161.         switch(order) {
  162.         case '1':
  163.             cout << "Creating arrays of " << n << " numbers in Ascending order" << endl;
  164.  
  165.             srand(time(0));
  166.             numbers[0] = rand();
  167.             for (int i = 1; i < n; i++) {
  168.                 numbers[i+1] = numbers[i] + rand();
  169.             }
  170.  
  171.             for (int i = 0; i < n; i++) {
  172.                 numbers2[i] = numbers[i];
  173.             }
  174.             applySort(numbers, numbers2, n);
  175.             break;
  176.  
  177.         case '2':
  178.             cout << "Creating arrays of " << n << " numbers in Descending order" << endl;
  179.             srand(time(0));
  180.             numbers[0] = rand();
  181.             for (int i = 1; i < n; i++) {
  182.                 numbers[i+1] = numbers[i] - rand();
  183.             }
  184.  
  185.             for (int i = 0; i < n; i++) {
  186.                 numbers2[i] = numbers[i];
  187.             }
  188.             applySort(numbers, numbers2, n);
  189.             break;
  190.  
  191.         case '3':
  192.             cout << "Creating arrays of " << n << " numbers in Random order" << endl;
  193.             srand(time(0));
  194.             for (int i = 0; i<n; i++) {
  195.                 numbers[i] = rand();
  196.             }
  197.  
  198.             for (int i = 0; i < n; i++) {
  199.                 numbers2[i] = numbers[i];
  200.             }
  201.             applySort(numbers, numbers2, n);
  202.             break;
  203.         }
  204.     }
  205.     return 0;
  206. }
  207.  
RAW Paste Data