SHARE
TWEET

Untitled

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