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

Question

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

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

Я уже собираюсь разбить большой файл tobesorted.txt на 3 файла из 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 из этих файлов в выходной файл в любой момент времени и продолжать объединять их, пока у меня не будет разобрано все начальное слово. Пример: объединение file0 с file1 приведет к выводу 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. Извините, если я сделал себя слишком трудно понять, английский не мой родной язык. Цени любую гепатит, который вы, ребята, можете дать.

Answer 1

Если вы уже разбили и отсортировали оригинальные файлы "чанков", вам нужно что-то вроде этого:

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);
}

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