Bisus

Untitled

Nov 20th, 2019
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. int read_array(const char *name, double *array, int n);
  5. void rand_array(double *array, int n);
  6. void print_array(double *array, int n);
  7. void swap(double *a, double *b);
  8. void f(double *a, int n);
  9.  
  10. /* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
  11.  * Турнирная сортировка или алгоритм heapsort.
  12.  * */
  13. void f(double *a, int n)
  14. {
  15.     int k, parent, position, i, child_1, child_2, child, width, width_dynamic, num_position;
  16.     double buffer;
  17.  
  18.     /* Рассматриваем бинаврное дерево с корнем a[0], где для любого a[k] потомками являются a[2*k + 1] и a[2*k + 2].
  19.      * Первый этап алгорима: превратить дерево в дерево, в котором всякая цепочка от корня до любого конечного элемента упорядочена по убыванию.
  20.      * */
  21.     for( k = 1; k<n; k++ )
  22.     {
  23.         // Поиск позиции, на которую должен перейти a[k]
  24.         for( position = k; position>0; position = parent )
  25.         {
  26.             parent = (int)( (position - 1)/2 );// Индекс родителя a[position]
  27.  
  28.             if( a[parent]>=a[k] )
  29.                 break;
  30.         }
  31.  
  32.         buffer = a[k];
  33.         for( i = k; i>position; i = parent )
  34.         {
  35.             parent = (int)( (i - 1)/2 );
  36.             a[i] = a[parent];
  37.         }
  38.         a[position] = buffer;
  39.     }
  40.     // Первый этап закончен. В a[0] находится максимальный элемент.
  41.  
  42.     /* Второй этап: для всех k = n - 1, .., 1: поменять местами a[0] и a[k], и в массиве первых k элементов массива a восстанавливаем структуру:
  43.      * всякая цепочка от корня до любого конечного элемента упорядочена по убыванию. */
  44.     for( k = n - 1; k>0; k-- )
  45.     {
  46.         swap(a, a + k);
  47.  
  48.         child_1 = 1;
  49.         child_2 = 2;
  50.         // Поиск позиции, на которую должен перейти a[0] в массиве a длины k
  51.         width = 1;// Число элементов на уровне дерева, на который будет переставлен a[0]
  52.         for( position = 0; position<(k - 1); child_1 = 2*position + 1, child_2 = 2*position + 2)
  53.         {
  54.             if( child_2>k )
  55.             {
  56.                 break;
  57.             }
  58.  
  59.             if( (child_2==k) )
  60.             {
  61.                 if( a[0]<a[child_1] )
  62.                 {
  63.                     position = child_1;
  64.                     width *= 2;
  65.                 }
  66.  
  67.                 break;
  68.             }
  69.  
  70.             if( (a[0]<a[child_1]) )
  71.             {
  72.                 if( a[child_1]<a[child_2] )
  73.                 {
  74.                     position = child_2;
  75.                 } else
  76.                 {
  77.                     position = child_1;
  78.                 }
  79.  
  80.                 width *= 2;
  81.                 continue;
  82.             }
  83.  
  84.             if( (a[0]<a[child_2]) )
  85.             {
  86.                 if( a[child_2]<a[child_1] )
  87.                 {
  88.                     position = child_1;
  89.                 } else
  90.                 {
  91.                     position = child_2;
  92.                 }
  93.  
  94.                 width *= 2;
  95.                 continue;
  96.             }
  97.  
  98.             break;// (a[position]>=a[child1]) && (a[position]>=a[child2])
  99.         }
  100.  
  101.         buffer = a[0];
  102.         width_dynamic = width;// Ширина уровня поддерева, в котором находится a[position]
  103.         num_position = position - width + 1;// Номер позиции в уровне поддерева ширины width_dynamic;
  104.         for( i = 0; i<position; width_dynamic = (int)(width_dynamic/2) )
  105.         {
  106.             if( num_position<(int)(width_dynamic/2) )
  107.             {
  108.                 child = 2*i + 1;
  109.             } else
  110.             {
  111.                 child = 2*i + 2;
  112.                 num_position -= (int)(width_dynamic/2);
  113.             }
  114.  
  115.             swap(a + i, a + child);
  116.             i = child;
  117.         }
  118.         a[position] = buffer;
  119.     }
  120. }
  121.  
  122. void swap(double *a, double *b)
  123. {
  124.     double buffer;
  125.  
  126.     buffer = *a;
  127.     *a = *b;
  128.     *b = buffer;
  129. }
  130.  
  131. /* Предполагается, что n>0 и по указателю array выделена память для n элементов.
  132.  * Ф-ия возвращает:
  133.  * -2, если не удалось прочитать элемент;
  134.  * -1, если не удалось открыть файл;
  135.  * 0, в случае успешного завершения.
  136.  * */
  137. int read_array(const char *name, double *array, int n)
  138. {
  139.     FILE *input;
  140.     int i;
  141.  
  142.     if( !(input = fopen(name, "r")) )
  143.         return -1;
  144.  
  145.     for( i = 0; i<n; i++ )
  146.     {
  147.         if( fscanf(input, "%lf", array + i)!=1 )
  148.         {
  149.             fclose(input);
  150.             return -2;
  151.         }
  152.     }
  153.  
  154.     fclose(input);
  155.     return 0;
  156. }
  157.  
  158. /* Предполагается, что n>0 и по указателю array выделена память для n элементов. */
  159. void rand_array(double *array, int n)
  160. {
  161.     int i;
  162.  
  163.     for( i = 0; i<n; i++ )
  164.         array[i] = rand();
  165. }
  166.  
  167. /* Предполагается, что n>0 и по указателю array выделена память для n элементов.
  168.  * */
  169. void print_array(double *array, int n)
  170. {
  171.     int i;
  172.  
  173.     if( n>20 )
  174.         n = 20;
  175.  
  176.     for( i = 0; i<n; i++ )
  177.         printf("Array[%d]=%lf\n", i, array[i]);
  178. }
  179.  
  180. int main(int argc, const char *argv[])
  181. {
  182.     int n, result_read;
  183.     double *a;
  184.     time_t time_begin;
  185.  
  186.     if( ((argc!=2) && (argc!=3)) || (sscanf(argv[1], "%d", &n)!=1) || (n<=0) )
  187.     {
  188.         fprintf(stderr, "Usage: %s size_of_array [file_with_array]\t\t([size_of_array]>0)\t(array is random if no file_wint_array)\n", argv[0]);
  189.         return 1;
  190.     }
  191.  
  192.     if( !(a = (double *)malloc(n*sizeof(double))) )
  193.     {
  194.         fprintf(stderr, "Can not allocate memory!\n");
  195.         return 2;
  196.     }
  197.     // Память выделена
  198.  
  199.     if( argc==3 )
  200.     {
  201.         result_read = read_array(argv[2], a, n);
  202.         if( result_read<0 )
  203.         {
  204.             switch( result_read )
  205.             {
  206.             case -2:
  207.                 fprintf(stderr, "Can not read element from %s\n", argv[2]);
  208.                 break;
  209.             case -1:
  210.                 fprintf(stderr, "Can not open file %s\n", argv[2]);
  211.                 break;
  212.             default:
  213.                 fprintf(stderr, "Unknown error %d in file %s\n", result_read, argv[2]);
  214.             }
  215.  
  216.             free(a);
  217.             return 3;
  218.         }
  219.     } else
  220.     {
  221.         rand_array(a, n);
  222.     }
  223.     // Массив считан или сгенерирован случайный
  224.  
  225.     printf("Array a[]:\n");
  226.     print_array(a, n);
  227.  
  228.     time_begin = clock();
  229.     f(a, n);
  230.     printf("Time: %.2f seconds\nArray a[]:\n", ( (float)(clock() - time_begin) )/CLOCKS_PER_SEC);
  231.     print_array(a, n);
  232.  
  233.     free(a);
  234.     return 0;
  235. }
RAW Paste Data