В случае простого слияния частичная упорядоченность сортируемых данных не дает никакого преимущества. Это объясняется тем, что на каждом проходе сливаются серии фиксированной длины. При естественном слиянии длина серий не ограничивается, а определяется количеством элементов в уже упорядоченных подпоследовательностях, выделяемых на каждом проходе.
Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.
Алгоритм сортировки естественным слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2. Распределение происходит следующим образом: поочередно считываются записи ai исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(ai)<=f(ai+1), то они записываются в первый вспомогательный файл f1. Как только встречаются f(ai)>f(ai+1), то записи ai+1 копируются во второй вспомогательный файл f2. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом серии образуют упорядоченные последовательности.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2.
Шаг 4. Повторяя шаги, сливаем упорядоченные серии до тех пор, пока не будет упорядочен целиком весь файл.
Символ "`" обозначает признак конца серии.
Признаками конца сортировки естественным слиянием являются следующие условия:
· количество серий равно 1 (определяется на фазе слияния).
· при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу, называется сбалансированным слиянием, в противном случае – несбалансированное слияние.
Реализация сортировки двухпутевым двухфазным естественным слиянием
Sort.h
#pragma once
class NMS {
private:
char name[255] = " ";
char tempFile1[255] = "NMSTemp1.txt";
char tempFile2[255] = "NMSTemp2.txt";
int fileLen2 = 1;
public:
NMS(char*);
int Split();
void Merge();
void PrintFiles();
};
Sort.cpp
#include "stdafx.h"
#include "Sort.h"
#include <iostream>
#include <cstdlib>
#include <fstream>
#define out ios::out
#define in ios::in
using namespace std;
NMS::NMS(char* fname) {
for (int i = 0; i < strlen(fname); i++) {
name[i] = fname[i];
}
//Проверка на отсортированность файла
while (fileLen2 > 0) {
fileLen2 = Split();
Merge();
}
}
//Функция разделения на 2 файла
int NMS::Split() {
int a1, a2;
int check = 0;
//Флаг для проверки если следующее число меньше текущего
bool flag = true;
ifstream fin(name, in);
ofstream fout1(tempFile1, out);
ofstream fout2(tempFile2, out);
if (!fin.is_open()) // если файл не открыт
cout << "Файл не может быть открыт!\n"; // сообщить об этом
else {
fin >> a1;
fout1 << a1 << " ";
while (!fin.eof()) {
fin >> a2;
//если следующий элемент меньше текущего меняем флаг
if (a2 < a1) {
if (flag) {
fout1 << "` ";
}
else {
fout2 << "` ";
}
flag =!flag;
}
if (flag) {
a1 = a2;
fout1 << a1 << " ";
}
else {
a1 = a2;
fout2 << a1 << " ";
check++;
}
}
if (fin.eof())
flag == true? fout1 << "`": fout2 << "`";
}
fin.close();
fout1.close();
fout2.close();
cout << "-------------Разделение-------------\n";
PrintFiles();
return check;
}
//Функция слияния
void NMS::Merge() {
char a1[255], a2[255];
ifstream fin1(tempFile1, in);
ifstream fin2(tempFile2, in);
ofstream fout(name, out);
if (!fin1.is_open()) // если файл не открыт
cout << "Временный файл 1 не может быть открыт!\n"; // сообщить об этом
else {
if (!fin2.is_open()) // если файл не открыт
cout << "Временный файл 2 не может быть открыт!\n"; // сообщить об этом
else {
//Если оба файла не закончились
while (!fin1.eof() &&!fin2.eof()) {
fin1 >> a1;
fin2 >> a2;
while ((strcmp(a1, "`")!= 0 || strcmp(a2, "`")!= 0) && (!fin1.eof() &&!fin2.eof())) {
//Если дошли до конца блока то пока не дошли до конца другого блока переписываем элементы в исходный файл
if (strcmp(a1, "`") == 0) {
while (strcmp(a2, "`")!= 0) {
fout << " " << a2;
fin2 >> a2;
}
}
else if (strcmp(a2, "`") == 0) {
while (strcmp(a1, "`")!= 0) {
fout << " " << a1;
fin1 >> a1;
}
}
//Сравниваем элементы и записываем в файл
if (atoi(a1) <= atoi(a2) && strcmp(a1, "`")!= 0 && strcmp(a2, "`")!= 0) {
fout << " " << a1;
fin1 >> a1;
}
else if (atoi(a1) > atoi(a2) && strcmp(a1, "`")!= 0 && strcmp(a2, "`")!= 0) {
fout << " " << a2;
fin2 >> a2;
}
}
}
//Если дошли до конца одного файла, переносим оставшиеся элементы из другого файла в исходный
while (!fin1.eof()) {
if (strcmp(a1, "`") == 0) {
fin1 >> a1;
}
else {
fout << " " << a1;
fin1 >> a1;
}
}
//Если дошли до конца одного файла, переносим оставшиеся элементы из другого файла в исходный
while (!fin2.eof()) {
if (strcmp(a2, "`") == 0) {
fin2 >> a2;
}
else {
fout << " " << a2;
fin2 >> a2;
}
}
}
}
fin1.close();
fin2.close();
fout.close();
cout << "-------------Слияние-------------\n";
PrintFiles();
}
void NMS::PrintFiles() {
char onScreen[255];
ifstream mfin(name, in);
ifstream fin1(tempFile1, in);
ifstream fin2(tempFile2, 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;
mfin.close();
fin1.close();
fin2.close();
}