ToniDev

MergeSort - Recursiv

Jan 31st, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include < iostream >
  2. using namespace std;
  3.  
  4. void merge(int arr[], int l, int m, int r) {
  5.     int i = l;
  6.     int j = m + 1;
  7.     int k = l;
  8.  
  9.     /* create temp array */
  10.     int temp[5];
  11.  
  12.     while (i <= m && j <= r) {
  13.         if (arr[i] <= arr[j]) {
  14.             temp[k] = arr[i];
  15.             i++;
  16.             k++;
  17.         }
  18.         else {
  19.             temp[k] = arr[j];
  20.             j++;
  21.             k++;
  22.         }
  23.  
  24.     }
  25.  
  26.     /* Copy the remaining elements of first half, if there are any */
  27.     while (i <= m) {
  28.         temp[k] = arr[i];
  29.         i++;
  30.         k++;
  31.  
  32.     }
  33.  
  34.     /* Copy the remaining elements of second half, if there are any */
  35.     while (j <= r) {
  36.         temp[k] = arr[j];
  37.         j++;
  38.         k++;
  39.     }
  40.  
  41.     /* Copy the temp array to original array */
  42.     for (int p = l; p <= r; p++) {
  43.         arr[p] = temp[p];
  44.     }
  45. }
  46.  
  47. /* l is for left index and r is right index of the
  48.    sub-array of arr to be sorted */
  49. void mergeSort(int arr[], int l, int r) {
  50.     if (l < r) {
  51.         // find midpoint
  52.         int m = (l + r) / 2;
  53.  
  54.         // recurcive mergesort first and second halves
  55.         mergeSort(arr, l, m);
  56.         mergeSort(arr, m + 1, r);
  57.  
  58.         // merge
  59.         merge(arr, l, m, r);
  60.     }
  61. }
  62.  
  63. int main() {
  64.     int myarray[5];
  65.     //int arr_size = sizeof(myarray)/sizeof(myarray[0]);
  66.     int arr_size = 5;
  67.  
  68.     cout << "Enter 5 integers in any order: " << endl;
  69.     for (int i = 0; i < 5; i++) {
  70.         cin >> myarray[i];
  71.     }
  72.     cout << "Before Sorting" << endl;
  73.     for (int i = 0; i < 5; i++) {
  74.         cout << myarray[i] << " ";
  75.     }
  76.     cout << endl;
  77.     mergeSort(myarray, 0, (arr_size - 1)); // mergesort(arr,left,right) called
  78.  
  79.     cout << "After Sorting" << endl;
  80.     for (int i = 0; i < 5; i++) {
  81.         cout << myarray[i] << " ";
  82.     }
  83.  
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment