Есть файл, который может содержать 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;
}

_>...
_>

char iwasthere[32768 / 8] = {}; // 4Кб
while (ifil >> num)
    iwasthere[num / 8] |= (1 << (num % 8));
for (int i = 0; i < 32768; ++i)
    if (iwasthere[i / 8] & (1 << (i % 8)))
        ofil << i << endl;

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

#include <string.h>

/*
    Read data from stdin, sort it
    (RAM usage is strongly limited)
    and write data to stdout.
    Data  values are integers in range 1..32768
    (NB! Zero value is excluded, each input value
    in sequence is unique, non-repetitive).
    Algorithm doesn't store input data in buffer,
    it stores one bit for each possible value, indicating
    whether this particular value was encountered or not.
*/

/* RAM buffer size (in bytes)*/
#define BUF_SIZE 4096
/* Value type */
typedef unsigned VAL_T;
/* Iterator type */
typedef unsigned ITER_T;
/* Single data value format string, is used by printf/scanf */
#define VAL_FMT "%u\n"
/* Get particular bit in particular byte value*/
#define GET_BIT (buf[byte_pos] & (MASKS[bit_pos]))

/* Application entry point */
int main(int argc, char* argv[]) {
    
    /* Masks used to select single bit from the byte */
    static unsigned char MASKS[8] = {1, 2, 4, 8, 16, 32, 64, 128};

    /* Input data buffer */
    static unsigned char buf[BUF_SIZE];
    memset(buf, 0, BUF_SIZE);
    /*
        Read input data from stdin and accumulate it into buffer
        in compressed form
    */
    {
        VAL_T value;
        while (scanf(VAL_FMT, &value) == 1) {
            ITER_T byte_pos, bit_pos;
            if (!value) {
                fprintf(stderr, "Input data s.b. > 0\n");
                exit(EXIT_FAILURE);
            };
            --value;
            byte_pos = value / 8;
            bit_pos = (value % 8);
            if (GET_BIT) {
                fprintf(stderr, "Input data is duplicated\n");
                exit(EXIT_FAILURE);
            };
            buf[byte_pos] |= MASKS[bit_pos];
        };
    };
    
    /*
        Write accumulated data to stdout
    */
    {
        ITER_T byte_pos, bit_pos;
        for (byte_pos = 0; byte_pos < BUF_SIZE; ++byte_pos)
            for (bit_pos = 0; bit_pos < 8; ++bit_pos)
                if (GET_BIT)
                    printf(VAL_FMT, byte_pos * 8 + bit_pos + 1);
    };
    
    return EXIT_SUCCESS;
}

1. Разработка архитектуры на макро или на микро-уровне (можно тут еще вспомнить недавние споры в этой же ветке форума на предмет — когда надо кидать исключение, когда возвращать код ошибки, а когда использовать assert)
   
2. Объектно-ориентированное программирование (паттерны)
   
3. Функциональное программирование
   
4. Организация работы программиста
   
5. Тестирование