#include <stdio.h>
#include <stdlib.h>
int read_array(const char *name, int n, double *a);
void init_arrray(int n, double *a);
void print_array(int n, double *a);
int find_place(double *a, int n, double x);
void swap(double *a, double *b);
void f(double *a, int n);

/* Предполагается, что n>0 и по указателю a расположен массив из n элементов.
 * Ф-ия возвращает i: a[i]<=x<=a[i + 1]. Если x меньше или равен всех элементов, то возвращается нуль.
 * Если x больше всех, то возвращается n.
 * */
int find_place(double *a, int n, double x)
{
    int i = 0, j = n - 1;

    while( i<=j )
    {
        if( a[i]<x )// Ищем a[i]>=x
        {
            i++;
            continue;
        }

        if( a[j]>=x )// Ищем a[j]<x
        {
            j--;
            continue;
        }

        swap(a + i, a + j);

        i++;
        j--;
    }

    return i;
}

void swap(double *a, double *b)
{
    double buffer;

    buffer = *a;
    *a = *b;
    *b = buffer;
}

/* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
 * Быстра сортировка.
 * */
void f(double *a, int n)
{
    int place;

    if( n<2 )
        return;

    while( n>1 )
    {
        place = find_place(a, n, a[(int)(n/2)]);

        if( place==0 )// a[(int)(n/2)] меньше или равен всех элемментов
        {
            swap(a, a + (int)(n/2));
            a += 1;
            n -= 1;
        }

        if( place<=(n - place) )
        {
            f(a, place);
            a += place;
            n -= place;
        } else
        {
            f(a + place, n - place);
            n = place;
        }
    }
}

/* Предполагается, что n>0 и по указателю a выделена память для n элементов.
 * Ф-ия возвращает:
 * -2, если не удалось прочитать элемент;
 * -1, если не удалось открыть файл;
 * 0, в случае успешного завершения.
 * */
int read_array(const char *name, int n, double *a)
{
    FILE *input;
    int i;

    if( !(input = fopen(name, "r")) )
        return -1;

    for( i = 0; i<n; i++ )
    {
        if( fscanf(input, "%lf", a + i)!=1 )
        {
            fclose(input);
            return -2;
        }
    }

    fclose(input);
    return 0;
}

/* Предполагается, что n>0 и по указателю a выделена память для n элементов. */
void init_array(int n, double *a)
{
    int i;

    for( i = 0; i<n; i++ )
        a[i] = rand();
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов.
 * */
void print_array(int n, double *array)
{
    int i;

    if( n>20 )
        n = 20;

    for( i = 0; i<n; i++ )
        printf("Array[%d]=%lf\n", i, array[i]);
}

int main(int argc, const char *argv[])
{
    int n, result_read;
    double *a;

    if( ((argc!=2) && (argc!=3)) || (sscanf(argv[1], "%d", &n)!=1) || (n<=0) )
    {
        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]);
        return 1;
    }

    if( !(a = (double *)malloc(n*sizeof(double))) )
    {
        fprintf(stderr, "Can not allocate memory!\n");
        return 2;
    }
    // Память выделена

    if( argc==3 )
    {
        result_read = read_array(argv[2], n, a);
        if( result_read<0 )
        {
            switch( result_read )
            {
            case -2:
                fprintf(stderr, "Can not read element from %s\n", argv[2]);
                break;
            case -1:
                fprintf(stderr, "Can not open file %s\n", argv[2]);
                break;
            default:
                fprintf(stderr, "Unknown error %d in file %s\n", result_read, argv[2]);
            }

            free(a);
            return 3;
        }
    } else
    {
        init_array(n, a);
    }
    // Массив считан или сгенерирован случайный

    printf("Array readed. Array a[]:\n");
    print_array(n, a);

    f(a, n);
    printf("Result. Array a[]:\n");
    print_array(n, a);

    free(a);
    return 0;
}