Bisus

Untitled

Nov 15th, 2019
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int read_array(const char *name, int n, double *a);
  4. void init_arrray(int n, double *a);
  5. void print_array(int n, double *a);
  6. int find_place(double *a, int n, double x);
  7. void swap(double *a, double *b);
  8. void f(double *a, int n);
  9.  
  10. /* Предполагается, что n>0 и по указателю a расположен массив из n элементов.
  11.  * Ф-ия возвращает i: a[i]<=x<=a[i + 1]. Если x меньше или равен всех элементов, то возвращается нуль.
  12.  * Если x больше всех, то возвращается n.
  13.  * */
  14. int find_place(double *a, int n, double x)
  15. {
  16.     int i = 0, j = n - 1;
  17.  
  18.     while( i<=j )
  19.     {
  20.         if( a[i]<x )// Ищем a[i]>=x
  21.         {
  22.             i++;
  23.             continue;
  24.         }
  25.  
  26.         if( a[j]>=x )// Ищем a[j]<x
  27.         {
  28.             j--;
  29.             continue;
  30.         }
  31.  
  32.         swap(a + i, a + j);
  33.  
  34.         i++;
  35.         j--;
  36.     }
  37.  
  38.     return i;
  39. }
  40.  
  41. void swap(double *a, double *b)
  42. {
  43.     double buffer;
  44.  
  45.     buffer = *a;
  46.     *a = *b;
  47.     *b = buffer;
  48. }
  49.  
  50. /* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
  51.  * Быстра сортировка.
  52.  * */
  53. void f(double *a, int n)
  54. {
  55.     int place;
  56.  
  57.     if( n<2 )
  58.         return;
  59.  
  60.     while( n>1 )
  61.     {
  62.         place = find_place(a, n, a[(int)(n/2)]);
  63.  
  64.         if( place==0 )// a[(int)(n/2)] меньше или равен всех элемментов
  65.         {
  66.             swap(a, a + (int)(n/2));
  67.             a += 1;
  68.             n -= 1;
  69.         }
  70.  
  71.         if( place<=(n - place) )
  72.         {
  73.             f(a, place);
  74.             a += place;
  75.             n -= place;
  76.         } else
  77.         {
  78.             f(a + place, n - place);
  79.             n = place;
  80.         }
  81.     }
  82. }
  83.  
  84. /* Предполагается, что n>0 и по указателю a выделена память для n элементов.
  85.  * Ф-ия возвращает:
  86.  * -2, если не удалось прочитать элемент;
  87.  * -1, если не удалось открыть файл;
  88.  * 0, в случае успешного завершения.
  89.  * */
  90. int read_array(const char *name, int n, double *a)
  91. {
  92.     FILE *input;
  93.     int i;
  94.  
  95.     if( !(input = fopen(name, "r")) )
  96.         return -1;
  97.  
  98.     for( i = 0; i<n; i++ )
  99.     {
  100.         if( fscanf(input, "%lf", a + i)!=1 )
  101.         {
  102.             fclose(input);
  103.             return -2;
  104.         }
  105.     }
  106.  
  107.     fclose(input);
  108.     return 0;
  109. }
  110.  
  111. /* Предполагается, что n>0 и по указателю a выделена память для n элементов. */
  112. void init_array(int n, double *a)
  113. {
  114.     int i;
  115.  
  116.     for( i = 0; i<n; i++ )
  117.         a[i] = rand();
  118. }
  119.  
  120. /* Предполагается, что n>0 и по указателю array выделена память для n элементов.
  121.  * */
  122. void print_array(int n, double *array)
  123. {
  124.     int i;
  125.  
  126.     if( n>20 )
  127.         n = 20;
  128.  
  129.     for( i = 0; i<n; i++ )
  130.         printf("Array[%d]=%lf\n", i, array[i]);
  131. }
  132.  
  133. int main(int argc, const char *argv[])
  134. {
  135.     int n, result_read;
  136.     double *a;
  137.  
  138.     if( ((argc!=2) && (argc!=3)) || (sscanf(argv[1], "%d", &n)!=1) || (n<=0) )
  139.     {
  140.         fprintf(stderr, "Usage: %s size_of_array [file_with_array]\t\t([size_of_array]>0)\t(array is random if no file_with_array)\n", argv[0]);
  141.         return 1;
  142.     }
  143.  
  144.     if( !(a = (double *)malloc(n*sizeof(double))) )
  145.     {
  146.         fprintf(stderr, "Can not allocate memory!\n");
  147.         return 2;
  148.     }
  149.     // Память выделена
  150.  
  151.     if( argc==3 )
  152.     {
  153.         result_read = read_array(argv[2], n, a);
  154.         if( result_read<0 )
  155.         {
  156.             switch( result_read )
  157.             {
  158.             case -2:
  159.                 fprintf(stderr, "Can not read element from %s\n", argv[2]);
  160.                 break;
  161.             case -1:
  162.                 fprintf(stderr, "Can not open file %s\n", argv[2]);
  163.                 break;
  164.             default:
  165.                 fprintf(stderr, "Unknown error %d in file %s\n", result_read, argv[2]);
  166.             }
  167.  
  168.             free(a);
  169.             return 3;
  170.         }
  171.     } else
  172.     {
  173.         init_array(n, a);
  174.     }
  175.     // Массив считан или сгенерирован случайный
  176.  
  177.     printf("Array readed. Array a[]:\n");
  178.     print_array(n, a);
  179.  
  180.     f(a, n);
  181.     printf("Result. Array a[]:\n");
  182.     print_array(n, a);
  183.  
  184.     free(a);
  185.     return 0;
  186. }
RAW Paste Data