_>Есть файл, который может содержать 32768 целых, неповторяющихся чисел в диапазоне от 1 до 32768.

_>Есть файл, который может содержать 32768 целых, неповторяющихся чисел в диапазоне от 1 до 32768.

_>>Есть файл, который может содержать 32768 целых, неповторяющихся чисел в диапазоне от 1 до 32768.

_>Есть файл, который может содержать 32768 целых, неповторяющихся чисел в диапазоне от 1 до 32768. Числа в файле расположены случайным образом. Написать программу, осуществляющую сортировку данного файла, результатом которой будет файл с отсортированными по возрастанию числами. Для осуществления сортировки разрешено использовать максимально 4Кб оперативной памяти.

_>#include <stdio.h>
_>#include <stdlib.h>

_>#include <string.h>
_>#include <assert.h>

_>/*
_>    Merge-sort algorithm implementation.
_>    Application read data from stdin, sort it using merge-sort
_>    with RAM usage limitation and write data to stdout.
_>    Data  values are integers in range 1..32768
_>    (NB! Zero value is excluded).
_>*/

_>/* RAM buffer size (in bytes)*/
_>#define BUF_RAW_SIZE 4096
_>/* Input values total number limit */
_>#define NUM_VALUES_MAX 32768
_>/* Value type */
_>typedef unsigned VAL_T;
_>/* Iterator type */
_>typedef unsigned ITER_T;
_>/* Size of one input value (in bytes) */
_>#define VAL_SIZE sizeof(VAL_T)
_>/* RAM buffer size (in input values) */
_>#define BUF_SIZE (BUF_RAW_SIZE / VAL_SIZE)
_>/* Temporary files quantity limit */
_>#define NUM_TMP_FILES_MAX (NUM_VALUES_MAX / BUF_SIZE + 1)
_>/* Single data value format string, is used by printf/scanf */
_>#define VAL_FMT "%u\n"
_>/* Cast some arbitrary pointer to (VAL_T*) and dereference it */
_>#define VAL_DEREF(Z) (*((const VAL_T*)Z))

_>/* Struct represents data stored in the temporary file */
_>typedef struct {
_>    /*
_>        Temporary file associated with data,
_>        NULL if file is not created or was exhausted
_>    */
_>    FILE* pfile;
_>    /*
_>        Stack top value, is 0 if no data is present;
_>        NB! We rely, that each data value is >= 1
_>    */
_>    VAL_T top;
_>} OnDiskStack;

_>/* Size of one OnDiskStack instance */
_>#define ODS_SIZE (sizeof(OnDiskStack))
_>/* Get the top value of OnDiskStack instance given by pointer to. */
_>#define ODSREF_TOP(Z) (((const OnDiskStack*)Z)->top)

_>/*
_>    Predicate, compares two VAL_T values,
_>    is needed by std library qsort algorithm.
_>    See qsort info for detailes.
_>*/
_>int compare(const void* a, const void* b) {
_>    return (VAL_DEREF(a) > VAL_DEREF(b)) - (VAL_DEREF(a) < VAL_DEREF(b));
_>}

_>/*
_>    Predicate, compares two OnDiskStack instances by
_>    top values. Is used by std library qsort algorithm
_>    and also at stacks resorting (see main(), resort() functions).
_>    Truth table:
        a->>top  |   b->top  | compare_s(a, b)
_>    ------------+-----------+-----------------
_>         0      |     0     |       0
_>    ------------+-----------+-----------------
_>       S!=0     |     0     |      -1
_>    ------------+-----------+-----------------
_>         0      |   S!=0    |       1
_>    ------------+-----------+-----------------
_>        S1      |    S2     | compare(S1, S2)
_>*/
_>int compare_s(const void* a, const void* b) {
_>    return
_>        compare(&ODSREF_TOP(a), &ODSREF_TOP(b)) *
_>        ((ODSREF_TOP(a) && ODSREF_TOP(b)) ? 1: -1);
_>}

_>/*
_>    Sort data in ascending order by std library qsort
_>    and place to OnDiskStack (i.e. to temporary file);
_>    Arguments:
_>        buf - pointer to data buffer;
_>        size - buffer size;
_>        stack - pointer to destination stack (
_>            stack s.b. empty, with no temporary file associated,
_>            stack data would be lost otherwise
_>        ).
_>*/
_>void sortnflush (
_>    VAL_T* buf, ITER_T size,
_>    OnDiskStack* stack
_>) {
_>    stack->pfile = NULL;
_>    stack->top = 0;
_>    switch (size) {
_>        case 1:
_>            stack->top = buf[0];
_>        case 0:
_>            break;
_>        default:
_>            if (!(stack->pfile = tmpfile())) {
_>                fprintf(stderr, "Temporary file creation failed\n");
_>                exit(EXIT_FAILURE);
_>            };
_>            qsort(buf, size, VAL_SIZE, compare);
_>            stack->top = buf[0];
_>            /*
_>                HACK! Write operation may be interrupted
_>                in some cicrcuimstances, but we treat
_>                such situation as an error
_>            */
_>            if (fwrite(&buf[1], VAL_SIZE, size - 1, stack->pfile) != (size - 1)) {
_>                fprintf(stderr, "Temporary file write failed\n");
_>                exit(EXIT_FAILURE);
_>            };
_>            rewind(stack->pfile);
_>            break;
_>    };
_>}

_>/*
_>    Stacks resorting.
_>    Stacks [1..(num_stacks - 1)] are assumed to be sorted.
_>    Find the place to insert the first stack, and do insert.
_>*/
_>void resort(OnDiskStack* stacks, ITER_T num_stacks) {
_>    OnDiskStack buf_stack;
_>    switch (num_stacks) {
_>        case 2:
_>            if (compare_s(&stacks[0], &stacks[1]) == 1) {
_>                buf_stack = stacks[0];
_>                stacks[0] = stacks[1];
_>                stacks[1] = buf_stack;
_>            };
_>        case 0:
_>            ;
_>        case 1:
_>            break;
_>        default:
_>            if (compare_s(&stacks[0], &stacks[1]) == 1) {
_>                ITER_T beg = 1;
_>                ITER_T end = num_stacks;
_>                ITER_T mid;
_>                buf_stack = stacks[0];
_>                /*
_>                    Search the place to insert stacks[0] in
_>                    range [beg, end)
_>                */
_>                do {
_>                    mid = (end + beg) / 2;
_>                    switch (compare_s(&buf_stack, &stacks[mid])) {
_>                        case 0:
_>                            beg = end = mid;
_>                            break;
_>                        case 1:
_>                            beg = mid;
_>                            break;
_>                        case -1:
_>                            end = mid;
_>                            break;
_>                        default:
_>                            /* We should never go here */
_>                            assert(0);
_>                            break;
_>                    };
_>                } while ((end - beg) > 1);
_>                memmove(stacks, &stacks[1], beg * ODS_SIZE);
_>                stacks[beg] = buf_stack;
_>            };
_>            break;
_>    };
_>}

_>/* Application entry point */
_>int main(int argc, char* argv[]) {

_>    /* On-disk stacks to store sorted portions of input data */
_>    static OnDiskStack stacks[NUM_TMP_FILES_MAX];
_>    /* Actual number of temporary storages used */
_>    ITER_T num_stacks;
    
_>    /*
_>        Read input data to buffer, sort buffer
_>        and put to on-disk stack when buffer is full or
_>        when stdin is terminated
_>    */
_>    {
_>        /* Input data buffer */
_>        static VAL_T buf[BUF_SIZE];
_>        /* Actual number of items stored in buffer*/
_>        ITER_T num_bufd = num_stacks = 0;
        
_>        int scan_ok;
_>        do {
_>            scan_ok = (scanf(VAL_FMT, &buf[num_bufd]) == 1);
_>            if (scan_ok) {
_>                if (!buf[num_bufd]) {
_>                    fprintf(stderr, "Input data s.b. > 0\n");
_>                    exit(EXIT_FAILURE);
_>                };
_>                ++num_bufd;
_>            };
_>            if ((BUF_SIZE == num_bufd) || (!scan_ok)) {
_>                if (NUM_TMP_FILES_MAX == num_stacks) {
_>                    fprintf(stderr, "Input data limit exceeded\n");
_>                    exit(EXIT_FAILURE);
_>                };
_>                sortnflush(buf, num_bufd, &stacks[num_stacks]);
_>                num_stacks++;
_>                num_bufd = 0;
_>            };
_>        } while (scan_ok);
_>    };
    
_>    /*
_>        Merge all data in stacks, write data to stdout
_>    */
_>    if (!num_stacks)
_>        return EXIT_SUCCESS;
_>    {
_>        qsort(stacks, num_stacks, ODS_SIZE, compare_s);
_>        while (stacks[0].top) {
_>            printf(VAL_FMT, stacks[0].top);
_>            if (!stacks[0].pfile) {
_>                stacks[0].top = 0;
_>            } else if (fread(&stacks[0].top, VAL_SIZE, 1, stacks[0].pfile) != 1) {
_>                if (feof(stacks[0].pfile)) {
_>                    stacks[0].pfile = NULL;
_>                    stacks[0].top = 0;
_>                } else {
_>                    fprintf(stderr, "Temporary file read failed\n");
_>                    exit(EXIT_FAILURE);
_>                };
_>            };
_>            resort(stacks, num_stacks);
_>        };
_>    };
_>    return EXIT_SUCCESS;
_>}

_>