fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h> 
  4.  
  5. char str[] = "%u %u %u %u %u %u %u %u %u %u \n";
  6.  
  7. struct dividearrays
  8. {
  9.     unsigned int * begin;
  10.     unsigned int * middle;
  11.     unsigned int * end;
  12. };
  13.  
  14. // Функция принимает в качестве аргументов:
  15. //// Указатель на начало массива, указатель на точку разделения,
  16. //// указатель на конец массива
  17. // Функция сортирует массив, если части массива, разделенные точкой
  18. // разделения, сами отсортированы
  19.  
  20. void mergesort
  21.           (
  22.             unsigned int * array,
  23.             unsigned int * split,
  24.             unsigned int * end
  25.           )
  26.  
  27. {
  28.     unsigned int *result = malloc((end-array)*sizeof(unsigned int));
  29.     unsigned int *result_ptr = result;
  30.     unsigned int *arr1, *arr2;
  31.     arr1 = array;
  32.     arr2 = split;
  33.     //printf(str, array[0], array[1], array[2], array[3], array[4],
  34.     //            array[5], array[6], array[7], array[8], array[9]); 
  35.  
  36.     while ( (arr1 != split) && (arr2 != end) )
  37.     {
  38.         if ( *arr1 > *arr2 )
  39.         {
  40.             *result_ptr = *arr2;
  41.             arr2++;
  42.         } else
  43.         {
  44.             *result_ptr = *arr1;
  45.             arr1++;
  46.         }
  47.     result_ptr++;
  48.     }
  49.     if (arr1  == split)
  50.     { //   назначение - result, источник - arr2, размер копирования - ...
  51.         memcpy(result_ptr, arr2, (end-arr2) * sizeof(unsigned int) );
  52.     } else
  53.     {
  54.         memcpy(result_ptr, arr1, (split-arr1)*sizeof(unsigned int) );
  55.     }    
  56.  
  57.     memcpy (array, result, (end-array)*sizeof(unsigned int) );
  58.     free (result);
  59. }
  60.  
  61. // Функция принимает в качестве аргументов начало и конецмассива
  62. // возвращает указатель на середину массива
  63.  
  64. unsigned int * findmiddle
  65.           (
  66.             unsigned int * array,
  67.             unsigned int * end
  68.           )
  69. {
  70.     unsigned int * middle = array + ( (end - array) / 2 );
  71.  
  72.     if ( middle == array )
  73.     {
  74.         return NULL;
  75.     }
  76.     return middle;
  77.  
  78. }
  79.  
  80.  
  81.  
  82.  
  83. int main(void)
  84. {
  85. /////////////
  86.  
  87.  
  88. /////////////
  89.  
  90.  
  91. unsigned int arr[] = { 3, 243, 1, 26, 1111, 16, 78, 17, 1, 66, 13333, 34646, 24, 234, 1832,
  92.                        13355, 234, 2761, 1, 666, 1337, 1488, 66666, 555, 1365, 136, 192, 256, 6566,
  93.                        13513, 1356,666666, 999  };
  94.  
  95.  
  96. unsigned int *middle;
  97. size_t end = sizeof(arr)/sizeof(arr[0]);
  98.  
  99. // массив, в котором будут
  100. // Начало, конец, середина.
  101.  
  102. struct dividearrays arr_div[33];
  103. struct dividearrays *arr_div_p1, *arr_div_p2;
  104.  
  105.  
  106.  
  107. size_t i;
  108.  
  109.  
  110. middle = findmiddle(arr, &arr[end]);
  111.  
  112. arr_div[0].begin  = arr;
  113. arr_div[0].middle = findmiddle(arr, &arr[end]);
  114. arr_div[0].end    = &arr[end];
  115.  
  116. arr_div_p1 = &arr_div[0];
  117. arr_div_p2 = &arr_div[1];
  118.  
  119. ///////////////////////
  120.     while ( arr_div_p1 != arr_div_p2 )
  121.     {
  122.  
  123.         // Если в результате деления первой половины массива на две
  124.         // мы не пытались делить массив размером 1
  125.         if ( findmiddle((*arr_div_p1).begin,  (*arr_div_p1).middle) != NULL )
  126.         {
  127.             // То тогда начало массива совпадает с началом того, который мы делим
  128.             arr_div_p2->begin  = arr_div_p1->begin;
  129.  
  130.             // Конец это серединка того массива, который мы делим
  131.             arr_div_p2->end    = findmiddle(arr_div_p1->begin,  arr_div_p1->end);
  132.  
  133.             // А его серединка это серединка между началом массива (этого) и концом массива (этого)
  134.             arr_div_p2->middle = findmiddle(arr_div_p2->begin, arr_div_p2->end);
  135.  
  136.             // Мы эту инфу записали в массив структур, и нам надо тогда записывать следующий в следующее
  137.             // Иначе бы мы повторно перезаписывали в то же место
  138.             arr_div_p2++;
  139.         }
  140.  
  141.  
  142.         // Если в результате деления второй половины массива на две
  143.         // мы не пытались делить массив размером 1        
  144.         if ( findmiddle((*arr_div_p1).middle, (*arr_div_p1).end   ) != NULL )
  145.         {
  146.             // Начало это серединка того массива, который мы делим
  147.             arr_div_p2->begin  = findmiddle(arr_div_p1->begin, arr_div_p1->end);
  148.  
  149.             // То тогда конец массива совпадает с концом того, который мы делим
  150.             arr_div_p2->end    = arr_div_p1->end;
  151.  
  152.             // А его серединка это серединка между началом массива (этого) и концом массива (этого)
  153.             arr_div_p2->middle = findmiddle(arr_div_p2->begin, arr_div_p2->end);
  154.  
  155.             // Мы эту инфу записали в массив структур, и нам надо тогда записывать следующий в следующее
  156.             // Иначе бы мы повторно перезаписывали в то же место
  157.             arr_div_p2++;
  158.         }
  159.  
  160.         // Переходим к следующей штуке, в которой есть начало середина конец
  161.         // Если ..., выйдем из этого цикла
  162.         arr_div_p1++;
  163.     }
  164. ///////////////////////
  165.  
  166.  
  167. while ( arr_div_p2 != &arr_div[0])
  168. {
  169.     arr_div_p2--; // <--- Теперь указатель стоит на одну ступеньку раньше, и он указывает на штуковину
  170.     mergesort(
  171.             arr_div_p2->begin,
  172.             arr_div_p2->middle,
  173.             arr_div_p2->end
  174.           );
  175. }
  176.  
  177.  
  178. for (i = 0; i < 33; i++)
  179. {
  180.   printf("%u ", arr[i]);
  181. }
  182.   printf("\n");
  183. ///////////////////////
  184.  
  185. return 0;
  186. }
  187.  
Success #stdin #stdout 0s 1920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 1 3 16 17 24 26 66 78 136 192 234 234 243 256 555 666 999 1111 1337 1356 1365 1488 1832 2761 6566 13333 13355 13513 34646 66666 666666
https://ideone.com/F8MypZ
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!