SHARE
TWEET

merge sort

I_LIKE_COFFEE Sep 20th, 2019 (edited) 121 in 355 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <malloc.h>
  5.  
  6.  
  7. void merge(int arr[], int l, int m, int r)//соединяем
  8. {
  9.     int i, j, k;
  10.     int n1 = m - l + 1;
  11.     int n2 = r - m;
  12.  
  13.     int* L = (int*)malloc(n1 * sizeof(int));
  14.     int* R = (int*)malloc(n2 * sizeof(int)); //временные массивы
  15.    
  16.    
  17.  
  18.     for (i = 0; i < n1; i++)
  19.         L[i] = arr[l + i];
  20.     for (j = 0; j < n2; j++)
  21.         R[j] = arr[m + 1 + j];
  22.  
  23.     printf("\nLeft part:\n");
  24.     for (int i = 0; i < n1; i++)
  25.         printf("%d ", L[i]);
  26.     printf("\nRight part:\n");
  27.     for (int i = 0; i < n2; i++)
  28.         printf("%d ", R[i]);
  29.     printf("\n");
  30.  
  31.     i = 0; // начальный индекс 1 подмассива
  32.     j = 0; // начальный индекс 2 подмассива
  33.     k = l; // начальный индекс объединенного подмассива
  34.  
  35.     while (i < n1 && j < n2)
  36.     {
  37.         if (L[i] <= R[j])
  38.         {
  39.             arr[k] = L[i];
  40.             i++;
  41.         }
  42.         else
  43.         {
  44.             arr[k] = R[j];
  45.             j++;
  46.         }
  47.         k++;
  48.     }
  49.  
  50.  
  51.     while (i < n1)//копируем оставшиеся элементы из L
  52.     {
  53.         arr[k] = L[i];
  54.         i++;
  55.         k++;
  56.     }
  57.  
  58.  
  59.     while (j < n2)//копируем оставшиеся элементы из R
  60.     {
  61.         arr[k] = R[j];
  62.         j++;
  63.         k++;
  64.     }
  65. }
  66.  
  67.  
  68. void mergeSort(int arr[], int l, int r)
  69. {
  70.     if (l < r)
  71.     {
  72.         int m = l + (r - l) / 2;
  73.  
  74.         mergeSort(arr, l, m);
  75.         mergeSort(arr, m + 1, r);
  76.  
  77.         merge(arr, l, m, r);
  78.     }
  79. }
  80.  
  81.  
  82.  
  83. int main()
  84. {
  85.     int n = 0;
  86.     scanf("%d", &n);
  87.  
  88.     int* arr = (int*)malloc(n * sizeof(int));
  89.     for (int i = 0; i < n; i++)
  90.         scanf("%d", &arr[i]);
  91.     printf("Initial array:\n");
  92.     for (int i = 0; i < n; i++)
  93.         printf("%d ", arr[i]);
  94.     printf("\n");
  95.  
  96.     mergeSort(arr, 0, n - 1);
  97.  
  98.     printf("\n\n");
  99.     for (int i = 0; i < n; i++)
  100.         printf("%d ", arr[i]);
  101.     printf("\n");
  102.     getchar();
  103.     return 0;
  104. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top