SHARE
TWEET

Untitled

Bisus Nov 22nd, 2019 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 "quicksort.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.     clock_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_with_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 readed. Array a[]:\n");
  129.     print_array(a, n);
  130.  
  131.     time_begin = clock();
  132.     quicksort(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. // quicksort.h
  143. #ifndef QUICKSORT_H
  144. #define QUICKSORT_H
  145.  
  146. void quicksort(double *a, int n, int (*p)(double, double));
  147.  
  148. #endif
  149.  
  150.  
  151.  
  152. // quicksort.c
  153. #include "quicksort.h"
  154. int find_place(double *a, int n, double x, int (*p)(double, double));
  155. void swap(double *a, double *b);
  156.  
  157. /* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
  158.  * Быстрая сортировка.
  159.  * */
  160. void quicksort(double *a, int n, int (*p)(double, double))
  161. {
  162.     int place;
  163.  
  164.     if( n<2 )
  165.         return;
  166.  
  167.     while( n>1 )
  168.     {
  169.         place = find_place(a, n, a[(int)(n/2)], p);
  170.  
  171.         if( place==0 )// a[(int)(n/2)] меньше или равен всех элементов
  172.         {
  173.             swap(a, a + (int)(n/2));
  174.             a += 1;
  175.             n -= 1;
  176.         }
  177.  
  178.         if( place<=(n - place) )
  179.         {
  180.             quicksort(a, place, p);
  181.             a += place;
  182.             n -= place;
  183.         } else
  184.         {
  185.             quicksort(a + place, n - place, p);
  186.             n = place;
  187.         }
  188.     }
  189. }
  190.  
  191. /* Предполагается, что n>0 и по указателю a расположен массив из n элементов.
  192.  * Ф-ия возвращает i: a[i]<=x<=a[i + 1]. Если x меньше или равен всех элементов, то возвращается нуль.
  193.  * Если x больше всех, то возвращается n.
  194.  * */
  195. int find_place(double *a, int n, double x, int (*p)(double, double))
  196. {
  197.     int i = 0, j = n - 1;
  198.  
  199.     while( i<=j )
  200.     {
  201.         if( p(x, a[i])>0 )// Ищем a[i]>=x
  202.         {
  203.             i++;
  204.             continue;
  205.         }
  206.  
  207.         if( p(a[j], x)>-1 )// Ищем a[j]<x
  208.         {
  209.             j--;
  210.             continue;
  211.         }
  212.  
  213.         swap(a + i, a + j);
  214.  
  215.         i++;
  216.         j--;
  217.     }
  218.  
  219.     return i;
  220. }
  221.  
  222. void swap(double *a, double *b)
  223. {
  224.     double buffer;
  225.  
  226.     buffer = *a;
  227.     *a = *b;
  228.     *b = buffer;
  229. }
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