|
|
От: |
slava_phirsov
|
|
| Дата: | 01.10.09 17:11 | ||
| Оценка: |
|
||
Есть файл, который может содержать 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;
}
