гпт

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

// Функция для разделения исходного файла на временные файлы
void splitFile(const std::string& inputFilename, const std::string& tempPrefix, int chunkSize) {
    // Открываем исходный файл для чтения
    std::ifstream inputFile(inputFilename);
    // Вектор для хранения временного чанка данных
    std::vector<std::string> chunk(chunkSize);

    int fileIndex = 0;
    // Читаем исходный файл и разделяем его на временные файлы
    while (!inputFile.eof()) {
        // Читаем chunkSize строк во временный чанк
        for (int i = 0; i < chunkSize && !inputFile.eof(); ++i) {
            std::getline(inputFile, chunk[i]);
        }

        // Если были прочитаны строки, выполняем сортировку и записываем во временный файл
        if (!chunk.empty()) {
            // Сортируем строки во временном чанке
            std::sort(chunk.begin(), chunk.end());

            // Генерируем имя временного файла
            std::string tempFilename = tempPrefix + std::to_string(fileIndex++) + ".txt";
            // Открываем временный файл для записи
            std::ofstream tempFile(tempFilename);
            // Записываем отсортированные строки во временный файл
            for (const std::string& line : chunk) {
                tempFile << line << std::endl;
            }
        }
    }

    // Закрываем исходный файл
    inputFile.close();
}

// Функция для выполнения слияния файлов
void mergeFiles(const std::string& outputFilename, const std::string& tempPrefix, int fileCount, int chunkSize) {
    // Открываем выходной файл для записи
    std::ofstream outputFile(outputFilename);
    // Вектор для хранения временных файлов
    std::vector<std::ifstream> tempFiles(fileCount);

    // Вектор для хранения текущих строк из каждого временного файла
    std::vector<std::string> currentLines(fileCount);
    // Вектор для отслеживания пустых файлов
    std::vector<bool> isFileEmpty(fileCount);

    // Открываем временные файлы и считываем первую строку из каждого файла
    for (int i = 0; i < fileCount; ++i) {
        // Генерируем имя временного файла
        std::string tempFilename = tempPrefix + std::to_string(i) + ".txt";
        // Открываем временный файл для чтения
        tempFiles[i].open(tempFilename);

        // Изначально считаем файлы не пустыми
        isFileEmpty[i] = false;

        // Считываем первую строку из файла
        if (!std::getline(tempFiles[i], currentLines[i])) {
            // Если файл закончился, помечаем его как пустой
            isFileEmpty[i] = true;
        }
    }

    // Выполняем слияние файлов
    while (true) {
        // Находим индекс файла с минимальным значением
        int minValueIndex = -1;
        for (int i = 0; i < fileCount; ++i) {
            // Если файл не пустой
            if (!isFileEmpty[i]) {
                // Если это первый не пустой файл или его строка меньше текущей минимальной строки
                if (minValueIndex == -1 || currentLines[i] < currentLines[minValueIndex]) {
                    // Обновляем индекс минимальной строки
                    minValueIndex = i;
                }
            }
        }

        // Если все файлы пусты, завершаем слияние
        if (minValueIndex == -1) {
            break;
        }

        // Записываем минимальную строку в выходной файл
        outputFile << currentLines[minValueIndex] << std::endl;

        // Считываем следующую строку из выбранного файла
        if (!std::getline(tempFiles[minValueIndex], currentLines[minValueIndex])) {
            // Если файл закончился, помечаем его как пустой
            isFileEmpty[minValueIndex] = true;
        }
    }

    // Закрываем все временные файлы
    for (int i = 0; i < fileCount; ++i) {
        tempFiles[i].close();

        // Удаляем временные файлы
        std::string tempFilename = tempPrefix + std::to_string(i) + ".txt";
        std::remove(tempFilename.c_str());
    }

    // Закрываем выходной файл
    outputFile.close();
}

// Функция для выполнения внешней сортировки методом естественного слияния
void externalSort(const std::string& inputFilename, const std::string& outputFilename, int chunkSize) {
    // Префикс для временных файлов
    std::string tempPrefix = "temp_chunk_";
    int fileCount = 0;

    // Разделяем исходный файл на временные файлы с заданным размером
    splitFile(inputFilename, tempPrefix, chunkSize);

    // Определяем количество созданных временных файлов
    std::ifstream inputFile(inputFilename);
    std::string line;
    while (std::getline(inputFile, line)) {
        ++fileCount;
    }
    inputFile.close();

    // Выполняем слияние файлов
    mergeFiles(outputFilename, tempPrefix, fileCount, chunkSize);
}

int main() {
    // Имя входного и выходного файлов
    std::string inputFilename = "input.txt";
    std::string outputFilename = "output.txt";
    // Размер временных чанков
    int chunkSize = 10000;

    // Генерируем случайный файл для сортировки
    std::ofstream inputFile(inputFilename);
    srand(time(nullptr));
    for (int i = 0; i < 100000; ++i) {
        int value = rand() % 1000000;
        inputFile << value << std::endl;
    }
    inputFile.close();

    // Выполняем внешнюю сортировку
    externalSort(inputFilename, outputFilename, chunkSize);

    std::cout << "External sort completed." << std::endl;

    return 0;
}