Задача многопутевого слияния разбить большой файл на несколько маленьких, все элементы которых смогут отсортироваться в оперативной памяти, а потом произвести слияние в исходный файл.
Реализация:
Sort.h
#pragma once
class MWBMS {
private:
char name[255] = " ";
char tempFile1[255] = "TempFile1.txt";
char tempFile2[255] = "TempFile2.txt";
char tempFile3[255] = "TempFile3.txt";
int s1, s2, s3;
public:
MWBMS(char*);
void Split();
void Merge();
void SortTemp(int*, int, int);
void PrintFiles();
};
Sort.cpp
#include "stdafx.h"
#include "Sort.h"
#include <cstring>
#include <fstream>
#include <iostream>
#include <cstdlib>
#define out ios::out
#define in ios::in
using namespace std;
//конструктор
MWBMS::MWBMS(char* fname) {
for (int i = 0; i < strlen(fname); i++) {
name[i] = fname[i];
}
Split();
Merge();
}
//Функция разделения
void MWBMS::Split() {
int a1;
int s = 0;
ifstream fin(name, in);
ofstream fout1(tempFile1, out);
ofstream fout2(tempFile2, out);
ofstream fout3(tempFile3, out);
if (!fin.is_open()) // если файл не открыт
cout << "Файл не может быть открыт!\n"; // сообщить об этом
else {
while (!fin.eof()) { //нахожу количество элементов в исходном файле
fin >> a1;
s++;
}
fin.clear();
fin.seekg(0);
if (s % 3 == 0) { //рассчитываю сколько элементов будет в каждом файле
s1 = s / 3;
s2 = s / 3;
s3 = s / 3;
}
else if (s % 3 == 1) {
s1 = s / 3 + 1;
s2 = s / 3;
s3 = s / 3;
}
else if (s % 3 == 2) {
s1 = s / 3 + 1;
s2 = s / 3 + 1;
s3 = s / 3;
}
//создание первого массива и его сортировка
int *arr1 = new int[s1]; // создание массива
for (int i = 0; i < s1; i++) {
fin >> a1; //добавление элементов из файла
arr1[i] = a1;
}
SortTemp(arr1, 0, s1 - 1); //сортировка элементов
for (int i = 0; i < s1; i++) { //запись в файл
fout1 << " " << arr1[i];
}
delete[] arr1;
//создание второго массива и его сортировка
int *arr2 = new int[s2];
for (int i = 0; i < s2; i++) {
fin >> a1;
arr2[i] = a1;
}
SortTemp(arr2, 0, s2 - 1);
for (int i = 0; i < s2; i++) {
fout2 << " " << arr2[i];
}
delete[] arr2;
//создание третьего массива и его сортировка
int *arr3 = new int[s3];
for (int i = 0; i < s3; i++) {
fin >> a1;
arr3[i] = a1;
}
SortTemp(arr3, 0, s3 - 1);
for (int i = 0; i < s3; i++) {
fout3 << " " << arr3[i];
}
delete[] arr3;
}
fin.close();
fout1.close();
fout2.close();
fout3.close();
PrintFiles();
}
//Функция слияния
void MWBMS::Merge() {
int a1, a2, a3;
//флаги для подсчета сколько элементов из файла были вытащены
int flag1, flag2, flag3;
ifstream fin1(tempFile1, in);
ifstream fin2(tempFile2, in);
ifstream fin3(tempFile3, in);
ofstream fout(name, out);
if (!fin1.is_open()) // если файл не открыт
cout << "Временный файл 1 не может быть открыт!\n"; // сообщить об этом
else {
if (!fin2.is_open()) // если файл не открыт
cout << "Временный файл 2 не может быть открыт!\n"; // сообщить об этом
else {
if (!fin3.is_open()) // если файл не открыт
cout << "Временный файл 3 не может быть открыт!\n"; // сообщить об этом
else {
fin1 >> a1;
fin2 >> a2;
fin3 >> a3;
flag1 = 1;
flag2 = 1;
flag3 = 1;
//если не достигнут конец одного из трех файлов нахождение минимального между тремя элементами
while ((!fin1.eof() &&!fin2.eof() &&!fin3.eof())||(flag1 <= s1 && flag2 <= s2 && flag3 <= s3)) {
if (a1 <= a2 && a1 <= a3) {
fout << " " << a1;
fin1 >> a1;
flag1++;
}
else if (a2 <= a1 && a2 <= a3) {
fout << " " << a2;
fin2 >> a2;
flag2++;
}
else if (a3 <= a1 && a3 <= a2) {
fout << " " << a3;
fin3 >> a3;
flag3++;
}
}
//если закончился один из файлов нахождение минимального между двумя элементами
if (fin1.eof()) {
while ((!fin2.eof() &&!fin3.eof())||(flag2 <= s2 && flag3 <=s3)) {
if (a2 <= a3) {
fout << " " << a2;
fin2 >> a2;
flag2++;
}
else {
fout << " " << a3;
fin3 >> a3;
flag3++;
}
}
}
else if (fin2.eof()) {
while ((!fin1.eof() &&!fin3.eof())|| (flag1 <= s1 && flag3 <= s3)) {
if (a1 <= a3) {
fout << " " << a1;
fin1 >> a1;
flag1++;
}
else {
fout << " " << a3;
fin3 >> a3;
flag3++;
}
}
}
else if (fin3.eof()) {
while ((!fin1.eof() &&!fin2.eof())|| (flag2 <= s2 && flag1 <= s1)) {
if (a1 <= a2) {
fout << " " << a1;
fin1 >> a1;
flag1++;
}
else {
fout << " " << a2;
fin2 >> a2;
flag2++;
}
}
}
//если достигнут конец двух файлов перенос оставшихся элементов
while (!fin1.eof() || flag1 <= s1) {
fout << " " << a1;
fin1 >> a1;
flag1++;
}
while (!fin2.eof() || flag2 <= s2) {
fout << " " << a2;
fin2 >> a2;
flag2++;
}
while (!fin3.eof() || flag3 <= s3) {
fout << " " << a3;
fin3 >> a3;
flag3++;
}
}
}
}
fout.close();
fin1.close();
fin2.close();
fin3.close();
PrintFiles();
}
//Быстрая сортировка
void MWBMS::SortTemp(int* s_arr, int first, int last) {
int i = first, j = last, x = s_arr[(first + last) / 2];
do {
while (s_arr[i] < x) i++;
while (s_arr[j] > x) j--;
if (i <= j) {
if (s_arr[i] > s_arr[j]) swap(s_arr[i], s_arr[j]);
i++;
j--;
}
} while (i <= j);
if (i < last)
SortTemp(s_arr, i, last);
if (first < j)
SortTemp(s_arr, first, j);
}
void MWBMS::PrintFiles() {
char onScreen[255];
ifstream mfin(name, in);
ifstream fin1(tempFile1, in);
ifstream fin2(tempFile2, in);
ifstream fin3(tempFile3, in);
cout << "Содержимое основного файла:\n";
mfin.getline(onScreen, 255);
cout << onScreen << endl;
cout << "Содержимое 1-го временного файла:\n";
fin1.getline(onScreen, 255);
cout << onScreen << endl;
cout << "Содержимое 2-го временного файла:\n";
fin2.getline(onScreen, 255);
cout << onScreen << endl;
cout << "Содержимое 3-го временного файла:\n";
fin3.getline(onScreen, 255);
cout << onScreen << endl;
mfin.close();
fin1.close();
fin2.close();
fin3.close();
}
III. Список использованной литературы
I. https://prog-cpp.ru/algorithm-sort/
II. https://www.intuit.ru/studies/courses/648/504/lecture/11473
III. Скиена С. Алгоритмы. Руководство по разработке