Как мне реализовать этот внешний алгоритм сортировки слиянием в C?

Мне нужно смоделировать внешний алгоритм сортировки, учитывая, что на машине доступно только 96 байт памяти. Я использую 32-байтовые структуры, которые выглядят так:

typedef struct {
    char usedmemory[31];
    char key;
}Register32;

Я уже разбил большой файл tobesorted.txt на три двоичных файла Register32. Например:

 I N T E R C A L A C A O B A L A N C E A D A

разделен на 8 файлов, которые сортируются внутри, в диапазоне от file0.bin до file7.bin, содержащих 31 байт мусора и 1 байт, являющийся ключом, который всегда используется для сортировки регистров.

file0.bin containing INT  
file1.bin containing CER  
file2.bin containing AAL  
file3.bin containing ACO  
file4.bin containing ABL  
file5.bin containing ACN  
file6.bin containing ADE  
file7.bin containing A

Мое задание состоит в том, чтобы «объединить» 2, 3 или 4 из этих файлов в выходной файл в любой момент времени и продолжать объединять их, пока я не разберусь с начальным словом. Пример: объединение файла0 с файлом1 выведет C E I N R T в выходной файл. Конечно, функция слияния должна быть обобщена, чтобы читать каждый ключ сортировки за раз и объединяться в выходной файл независимо от размера входного файла. Функция My Merge получает массив файлов, который может содержать 2, 3 или 4 файла (функция не знает), самый низкий индекс упомянутого массива, более высокий индекс и выходной файл. Это выглядит так:

void MergeFunction(TypeFile* entry, int lowerindex,int higherindex, TypeFile exitfile){
       int i, j, count = 0;
}

TypeFile является только typedef FILE* TypeFile;.

Я знаю, что должен сравнивать каждый ключ регистра за раз, а затем записывать самый низкий ключ в файл выхода, если мне нужно смоделировать ограничение памяти, но я не могу заставить себя придумать, как это сделать. Ограничения цикла и случаи, когда входные данные состоят из 6 или более ключевых символов, плавят мой мозг. В конце концов, я просто хочу полностью отсортировать этот первоначальный tobesorted.txt, объединяя 2, 3 или 4 файла за раз в один больший и переходя к следующему. Это уже реализовано, мне просто нужно реализовать функцию Merge. Извините, если я сделал себя слишком трудным для понимания, английский не мой родной язык. Цените любую помощь, которую вы, ребята, можете дать.


c sorting external-sorting
person Lucas Sartori    schedule 06.06.2017    source источник
comment
96 байт. Riiiiight.. Сколько вы собираетесь выделить в качестве пространства стека? С 96 байтами вы не сможете запустить ни одну из известных мне файловых систем. Даже FAT-12 требовался 512-байтовый буфер каталога.   -  person ThingyWotsit    schedule 06.06.2017
comment
@ThingyWotsit Я думаю, что ограничение в 96 байт находится в памяти системы, а не на диске. Это означает, что программа сортировки не должна использовать более 96 байт. Я могу ошибаться.   -  person Ajay Brahmakshatriya    schedule 06.06.2017
comment
так первые 31 байт вообще используются? Кажется, вы говорите, что они не являются частью ключа сортировки и не являются частью вывода, так зачем их вообще читать?   -  person Useless    schedule 06.06.2017
comment
@ Бесполезно, это всего лишь часть задания. Нам нужно сравнить материал, который имеет содержание, чтобы увидеть разницу между различными методами сортировки.   -  person Lucas Sartori    schedule 06.06.2017
comment
1. Вы действительно сравниваете эти данные? 2. Вы действительно выводите эти данные? Если оба ответа отрицательные, то задание требует от вас прочесть их в память?   -  person Useless    schedule 06.06.2017
comment
Структура подразумевает, что размер записи составляет 32 байта, и если для хранения записей доступно только 96 байт, памяти достаточно только для хранения 3 записей одновременно. Как эта программа должна иметь возможность объединять до 4 файлов одновременно?   -  person rcgldr    schedule 06.06.2017

Ответы (1)


arrow_upward
0
arrow_downward

Если вы уже разделили и отсортировали исходные файлы «фрагментов», вам нужно что-то вроде этого:

void mergeFiles(FILE* fIn1, FILE* fIn2, FILE* fOut)
{
    int ch1;
    int ch2;
    ch1 = fgetc(fIn1);
    ch2 = fgetc(fIn2);
    // merge files
    while ((ch1 != EOF) && (ch2 != EOF))
    {
        if (ch1 < ch2)
        {
            fputc(ch1, fOut);
            ch1 = fgetc(fIn1);
        }
        else
        {
            fputc(ch2, fOut);
            ch2 = fgetc(fIn2);
        }
    }

    // write the rest of one of the files
    if (ch2 == EOF)
    {
        while (ch1 != EOF)
        {
            fputc(ch1, fOut);
            ch1 = fgetc(fIn1);
        }
    }
    else
    {
        while (ch2 != EOF)
        {
            fputc(ch2, fOut);
            ch2 = fgetc(fIn2);
        }
    }
    fflush(fOut);
}

Идея состоит в том, что на этапе слияния алгоритма сортировки слиянием требуется получить только первые элементы каждого из двух объединяемых подмассивов. Таким образом, поток ввода (например, файл) также соответствует этим требованиям (т.е. вам не нужно считывать целые файлы в вашу оперативную память!). Все, что вам нужно сделать, это просто прочитать два отсортированных файла посимвольно, сравнить эти символы и вывести в целевой файл, в зависимости от того, что меньше. Затем вы снова объединяете эти новые объединенные файлы, пока не получите один большой отсортированный файл.

person SergGr    schedule 07.06.2017