Ii. Естественным слиянием




В случае простого слияния частичная упорядоченность сортируемых данных не дает никакого преимущества. Это объясняется тем, что на каждом проходе сливаются серии фиксированной длины. При естественном слиянии длина серий не ограничивается, а определяется количеством элементов в уже упорядоченных подпоследовательностях, выделяемых на каждом проходе.

Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.

Алгоритм сортировки естественным слиянием

Шаг 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();

}




Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: