Advertisement
Tark_Wight

Recurrent mergeSort for an array vector

Sep 3rd, 2023
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <ctime>
  6.  
  7.  
  8. const int SIZE{ 10 };  
  9.  
  10.  
  11. void merge(std::vector<int>& array, int left, int middle, int right) {
  12.     int numElementsLeft{ middle - left + 1 };
  13.     int numElementsRight{ right - middle };
  14.  
  15.     std::vector<int> leftArray(numElementsLeft);
  16.     std::vector<int> rightArray(numElementsRight);
  17.  
  18.     for (int index{}; index < numElementsLeft; ++index) {
  19.         leftArray[index] = array[left + index];
  20.     }
  21.  
  22.     for (int index{}; index < numElementsRight; ++index) {
  23.         rightArray[index] = array[middle + 1 + index];
  24.     }
  25.  
  26.     int i{}, j{}, k{ left };
  27.  
  28.     while (i < numElementsLeft && j < numElementsRight) {
  29.         if (leftArray[i] <= rightArray[j]) {
  30.             array[k] = leftArray[i];
  31.             ++i;
  32.         }
  33.         else {
  34.             array[k] = rightArray[j];
  35.             ++j;
  36.         }
  37.         ++k;
  38.     }
  39.  
  40.     while (i < numElementsLeft) {
  41.         array[k] = leftArray[i];
  42.         ++i;
  43.         ++k;
  44.     }
  45.  
  46.     while (j < numElementsRight) {
  47.         array[k] = rightArray[j];
  48.         ++j;
  49.         ++k;
  50.     }
  51. }
  52.  
  53.  
  54. void iterativeMergeSort(std::vector<int>& array) {
  55.     int numElements{ static_cast<int>(array.size()) };
  56.  
  57.     for (int currentSize{ 1 }; currentSize <= numElements - 1; currentSize *= 2) {
  58.         for (int leftStart{}; leftStart < numElements - 1; leftStart += 2 * currentSize) {
  59.             int middle{ std::min(leftStart + currentSize - 1, numElements - 1) };
  60.             int rightEnd{ std::min(leftStart + 2 * currentSize - 1, numElements - 1) };
  61.  
  62.             merge(array, leftStart, middle, rightEnd);
  63.         }
  64.     }
  65. }
  66.  
  67.  
  68. void handleFillArray() {
  69.     std::vector<int> array(SIZE);
  70.  
  71.     std::cout << "Original array (size is " << SIZE << "): ";
  72.     int temporal;
  73.     for (int& num : array) {
  74.         std::cin >> temporal;
  75.         num = temporal;
  76.     }
  77.  
  78.     iterativeMergeSort(array);
  79.  
  80.     std::cout << "Sorted array: ";
  81.     for (int num : array) {
  82.         std::cout << num << " ";
  83.     }
  84. }
  85.  
  86.  
  87. void randomAutoFillTest() {
  88.     std::vector<int> array;
  89.  
  90.    
  91.     std::random_device rd;
  92.     std::mt19937 gen(time(0));
  93.     std::uniform_int_distribution<int> dis(-100, 100);
  94.  
  95.     for (int index = 0; index < SIZE; ++index) {
  96.         array.push_back(dis(gen));
  97.     }
  98.  
  99.     std::cout << "Original array: ";
  100.     for (int num : array) {
  101.         std::cout << num << " ";
  102.     }
  103.  
  104.     iterativeMergeSort(array);
  105.  
  106.     std::cout << "\nSorted array: ";
  107.     for (int num : array) {
  108.         std::cout << num << " ";
  109.     }
  110. }
  111.  
  112.  
  113. void testModeSelection() {
  114.     std::cout << "Select the test mode: \n1. Manual input \n2. Auto input of random values \nmodeSelectionValue is ";
  115.     int modeSelectionValue;
  116.     std::cin >> modeSelectionValue;
  117.  
  118.     if (modeSelectionValue == 1) {
  119.         handleFillArray();
  120.     } else if (modeSelectionValue == 2) {
  121.         randomAutoFillTest();
  122.     } else {
  123.         std::cout << "Incorrect test mode value\n";
  124.     }
  125. }
  126.  
  127.  
  128. int main() {
  129.     testModeSelection();
  130.  
  131.     return 0;
  132. }
  133.  
Tags: C++ cpp mergesort
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement