Сортировка файлов естественным слиянием и сбалансированное многопутевое слияние

i.loser = &node[i]. e;

node[i]. i. parent = &node[i/2]. i;

node[i]. e. parent =(:iNodeTag*) &node[(nNodes + i)/2]. i;

node[i]. e. run = 0;

node[i]. e. valid = false;

}

win = &node[0]. e;

lastKeyValid = false;

if ((ifp = fopen (ifName, «rb»)) == NULL) {

printf («error: file %s, unable to openn», ifName);

cleanExit (1);

}

}

while (1) {

/* заместить предыдущего победителя новой записью */

if (!eof) {

int op1;

/*Читаем входной файл */

if (fscanf (ifp," %u", &op1)≠ EOF) {

win->rec.key = op1;

if ((!lastKeyValid — compLT (win->rec.key, lastKey))

&& (++win->run > maxRun))

maxRun = win->run;

win->valid = true;

} else if (feof (ifp)) {

fclose (ifp);

eof = true;

win->valid = false;

win->run = maxRun + 1;

} else {

perror («io4»);

cleanExit (1);

}

} else {

win->valid = false;

win->run = maxRun + 1;

}

/* привести в порядок предков победителя и проигравшего */

p = (iNodeTag*)win->parent;

do {

bool swap;

swap = false;

if (p->loser->run < win->run) {

swap = true;

} else if (p->loser->run == win->run) {

if (p->loser->valid && win->valid) {

if (compLT (p->loser->rec.key, win->rec.key))

swap = true;

} else {

swap = true;

}

}

if (swap) {

/* p должно быть победителем */

eNodeType *t;

t = p->loser;

p->loser = win;

win = t;

}

p = p->parent;

} while (p ≠ &node[0]. i);

/* конец прохода? */

if (win->run ≠ curRun) {

/* win->run = curRun + 1 */

if (win->run > maxRun) {

/* конец вывода */

free (node);

return NULL;

}

curRun = win->run;

}

/* вывести верх дерева */

if (win->run) {

lastKey = win->rec.key;

lastKeyValid = true;

return &win->rec;

}

}

}

void makeRuns (void) {

recType *win; /* победитель */

int fileT; /* прошлый файл */

int fileP; /* следующий за прошлым файлом */

int j; /* выбираем file[j] */

/* Сделать инициализационные проходы через выбор с замещением.

* Проходы напианы с использованием распределения Фибоначчи.

*/

/* инициализовать файловые структуры */

fileT = nTmpFiles — 1;

fileP = fileT — 1;

for (j = 0; j < fileT; j++) {

file[j]->fib = 1;

file[j]->dummy = 1;

}

file[fileT]->fib = 0;

file[fileT]->dummy = 0;

level = 1;

j = 0;

win = readRec ();

while (win) {

bool anyrun;

anyrun = false;

for (j = 0; win && j <= fileP; j++) {

bool run;

run = false;

if (file[j]->valid) {

if (!compLT (win->key, file[j]->rec.key)) {

/* добавить к существующему проходу */

run = true;

} else if (file[j]->dummy) {

/* начать новый проход */

file[j]->dummy—;

run = true;

}

} else {

/* первый проход в файле */

file[j]->dummy—;

run = true;

}

if (run) {

anyrun = true;

/* полный проход */

while (1) {

if (fwrite (win, sizeof (recType), 1, file[j]->fp) ≠ 1) {

perror («io3»);

cleanExit (1);

}

file[j]->rec.key = win->key;

file[j]->valid = true;

if ((win = readRec ()) == NULL) break;

if (compLT (win->key, file[j]->rec.key)) break;

}

}

}

/* Если нет места для проходов — вверх на уровень */

if (!anyrun) {

int t;

level++;

t = file[0]->fib;

for (j = 0; j <= fileP; j++) {

file[j]->dummy = t + file[j+1]->fib — file[j]->fib;

file[j]->fib = t + file[j+1]->fib;

}

}

}

}

void rewindFile (int j) {

/* Идти в начало file[j] и читать первую запись */

file[j]->eor = false;

file[j]->eof = false;

rewind (file[j]->fp);

if (fread (&file[j]->rec, sizeof (recType), 1, file[j]->fp) ≠ 1) {

if (feof (file[j]->fp)) {

file[j]->eor = true;

file[j]->eof = true;

} else {

perror («io5»);

cleanExit (1);

}

}

}

void mergeSort (void) {

int fileT;

int fileP;

int j;

tmpFileType *tfile;

/* Многофазная сортировка слиянием */

fileT = nTmpFiles — 1;

fileP = fileT — 1;

/* снабдить файлы информацией */

for (j = 0; j < fileT; j++) {

rewindFile (j);

}

/* Каждый проход по циклу сливает один проход */

while (level) {

while (1) {

bool allDummies;

bool anyRuns;

/* сканировать на предмет проходов */

allDummies = true;

anyRuns = false;

for (j = 0; j <= fileP; j++) {

if (!file[j]->dummy) {

allDummies = false;

if (!file[j]->eof) anyRuns = true;

}

}

if (anyRuns) {

int k;

keyType lastKey;

/* слить 1 проход file[0]. .file[P] —> в file[T] */

while (1) {

/* Каждый проход по циклу записывает 1 запись в file[fileT]*/

/* Найти наименьший ключ */

k = -1;

for (j = 0; j <= fileP; j++) {

if (file[j]->eor) continue;

if (file[j]->dummy) continue;

if (k < 0 -;

(k ≠ j && compGT (file[k]->rec.key, file[j]->rec.key)))

k = j;

}

if (k < 0) break;

/* записать record[k] в file[fileT] */

if (fwrite (&file[k]->rec, sizeof (recType), 1,

file[fileT]->fp) ≠ 1) {

perror («io6»);

cleanExit (1);

}

/* заменить record[k] */

lastKey = file[k]->rec.key;

if (fread (&file[k]->rec, sizeof (recType), 1,

file[k]->fp) == 1) {

/* проверить на предмет конца пробега file[s] */

if (compLT (file[k]->rec.key, lastKey))

file[k]->eor = true;

} else if (feof (file[k]->fp)) {

file[k]->eof = true;

file[k]->eor = true;

} else {

perror («io7»);

cleanExit (1);

}

}

/* Подкорректировкать холостые */

for (j = 0; j <= fileP; j++) {

if (file[j]->dummy) file[j]->dummy—;

if (!file[j]->eof) file[j]->eor = false;

}

} else if (allDummies) {

for (j = 0; j <= fileP; j++)

file[j]->dummy—;

file[fileT]->dummy++;

}

/* конец прохода */

if (file[fileP]->eof && !file[fileP]->dummy) {

/* completed a fibonocci-level */

level—;

if (!level) {

/* готово, file[fileT] содержит данные */

return;

}

/* fileP истощился, открываем новый такой же */

fclose (file[fileP]->fp);

if ((file[fileP]->fp = fopen (file[fileP]->name, «w+b»))

== NULL) {

perror («io8»);

cleanExit (1);

}

file[fileP]->eof = false;

file[fileP]->eor = false;

rewindFile (fileT);

/* f[0], f[1]. ., f[fileT] <— f[fileT], f[0]. ., f[T-1] */

tfile = file[fileT];

memmove (file + 1, file, fileT * sizeof (tmpFileType*));

file[0] = tfile;

/* начать новые проходы */

for (j = 0; j <= fileP; j++)

if (!file[j]->eof) file[j]->eor = false;

}

}

}

}

void extSort (void) {

initTmpFiles ();

makeRuns ();

mergeSort ();

termTmpFiles (0);

}

#ifdef __cplusplus

}

#endif