Advertisement
informaticage

Merge sort ansi C

May 24th, 2021 (edited)
1,020
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.60 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define LEN 10
  5. void merge(int *V, size_t left, size_t mid, size_t right);
  6. void merge_sort(int *V, size_t i, size_t j);
  7. void print_arr(int *V, size_t length);
  8.  
  9. int main(void) {
  10.   int arr[LEN] = {
  11.     4, 6, 10, 10, 1, 9, 11, 15, -1, 1
  12.   };
  13.  
  14.   printf("Unsorted:\n");
  15.   print_arr(arr, LEN);
  16.   merge_sort(arr, 0, LEN - 1);
  17.  
  18.   printf("\nSorted:\n");
  19.   print_arr(arr, LEN);
  20.   return 0;
  21. }
  22.  
  23. void print_arr(int *V, size_t length) {
  24.   printf("[ ");
  25.   for (size_t i = 0; i < length; i++)
  26.     printf("%d ", V[i]);
  27.   printf("]");
  28. }
  29.  
  30. void merge(int *V, size_t left, size_t mid, size_t right) {
  31.   int *T = (int *)malloc(sizeof(int) * (right - left + 1));
  32.   size_t i = left;
  33.   size_t j = mid + 1;
  34.   size_t t_index = 0;
  35.  
  36.   // Finchè non ho finito almeno una delle 2 fusioni
  37.   // T(n) = O(n)
  38.   while (i <= mid && j <= right) {
  39.     if (V[i] < V[j]) {
  40.       T[t_index++] = V[i++];
  41.     } else {
  42.       T[t_index++] = V[j++];
  43.     }
  44.   }
  45.  
  46.   // Ciò che rimane del left
  47.   // T(n) = O(n)
  48.   while (i <= mid) {
  49.     T[t_index++] = V[i++];
  50.   }
  51.  
  52.   // Ciò che rimane del right
  53.   // T(n) = O(n)
  54.   while (j <= right) {
  55.     T[t_index++] = V[j++];
  56.   }
  57.  
  58.   // Copiamo su V
  59.   for (size_t copy_i = left; copy_i <= right; copy_i++) {
  60.     V[copy_i] = T[copy_i - left];
  61.   }
  62. }
  63.  
  64. // T(N) = 2T(n/2) + O(n)
  65. // 2nd MT = n^logb(a)*log2n
  66. void merge_sort(int *V, size_t i, size_t j) {
  67.   if (i >= j)
  68.     return;
  69.  
  70.   size_t mid = i + (j - i) / 2;
  71.   // O(T(n / 2))
  72.   merge_sort(V, i, mid);
  73.  
  74.   // O(T(n / 2))
  75.   merge_sort(V, mid + 1, j);
  76.  
  77.   // O(n)
  78.   merge(V, i, mid, j);
  79. }
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement