Приступим. Закончив с рассмотрением основных внутренних алгоритмов сортировки, приступим к рассмотрению внешних алгоритмов. Одним из таких есть внешняя сортировка на 3 лентах или простое слияние
Прямое слияние
Слияние означает объединение двух (или более) последовательностей в одну-единственную упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов. Слияние намного проще сортировки, и его используют как вспомогательную операцию в более сложных процессах сортировки последовательностей. Одна из сортировок на основе слияния называется простым слиянием. Она выполняется следующим образом:
1. Последовательность (файл) a разбивается на две половины: b и c.
2. Части b и c сливаются, при этом одиночные элементы образуют упорядоченные пары.
3. Полученный файл под именем a вновь обрабатывается как указано в пунктах 1, 2; при этом упорядоченные пары переходят в такие же четверки.
4. Повторяя предыдущие шаги, сливаем четверки в восьмерки и т.д., каждый раз «удваивая» длину слитых подпоследовательностей до тех пор, пока не будет упорядочен целиком весь файл.
Ниже представлен код, который находится в заголовочном файле "functions.h"
#include <iostream>
#include <stdlib.h>
#include <fstream>
using namespace std;
//Prototypes:
void QuickSort(int l, int r, int *a, int n);
void Create_file(fstream&f, char* filename, int &filesize)
{
int x;
f.open(filename, ios::out|ios::binary);
cout << "Enter values please; to break type 9999" << endl;
cin >> x;
while(x!=9999)
{
f.write((char*)&x, sizeof x);
filesize++;
cin >> x;
}
f.close();
}
void Read_file(fstream&f, char* filename)
{
int x;
cout << endl;
f.open(filename, ios::in|ios::binary);
if(f.is_open())
{
if(f.eof())
{
f.clear();
f.seekg(0);
}
cout << "Content of : " << filename << endl;
while(f.read((char*)&x, sizeof x))
{
cout << x << " " ;
}
}
else
{
cout << "Error opening file" << endl;
exit(1);
}
cout << endl;
f.close();
}
void sort_a_to_bc(fstream&a, fstream&b, fstream&c, char* filename, int n)
{
int i=1, j, x;
a.open(filename, ios::in|ios::binary);
b.open("b.dat", ios::out|ios::binary);
c.open("c.dat", ios::out|ios::binary);
while(!a.eof())
{
if(i%2!=0)
{
j=1;
while(j<=n && a.read((char*)&x, sizeof x))
{
b.write((char*)&x, sizeof x);
j++;
}
}
else
{
j=1;
while(j<=n && a.read((char*)&x, sizeof x))
{
c.write((char*)&x, sizeof x);
j++;
}
}
i++;
}
a.close();
b.close();
c.close();
}
void sort_bc_to_a(fstream&a, fstream&b, fstream&c, char* filename, int n)
{
int i, j, z[20], aSize, x;
a.open(filename, ios::out|ios::binary);
b.open("b.dat", ios::in|ios::binary);
c.open("c.dat", ios::in|ios::binary);
while((b.eof()==0) || (c.eof()==0))
{
i = 0; j = 1;
while(b.eof()==0 && j<=n)
{
if(b.read((char*)&x, sizeof x))
{
i++;
z[i]=x;
}
else
break;
j++;
}
j = 1;
while(c.eof()==0 && j<=n)
{
if(c.read((char*)&x, sizeof x))
{
i++;
z[i]=x;
}
else
break;
j++;
}
aSize = i;
QuickSort(1, aSize, z, aSize);
for(i=1; i<=aSize; i++)
a.write((char*)&z[i], sizeof z[i]);
}
a.close();
b.close();
c.close();
}
void QuickSort(int l, int r, int *a, int n)
{
int i=l, j=r, x, w, k;
x = a[(l+r)/2];
do
{
while(a[i]<x)
i++;
while(x<a[j])
j--;
if(i<=j)
{
w = a[i];
a[i] = a[j];
a[j] = w;
i++;
j--;
}
}
while(i<=j);
if(l<j)
QuickSort(l, j, a, n);
if(i<r)
QuickSort(i, r, a, n);
}
и главный фал, в котором находится функция main
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include "functions.h"
using namespace std;
void main()
{
fstream f1, f2, f3;
int filesize=0, n = 1, i = 1;
char filename[20];
cout << "Enter filename please:";
cin >> filename;
Create_file(f1, filename, filesize);
cout << endl;
Read_file(f1, filename);
cout << endl << endl << endl;
while(n<filesize)
{
sort_a_to_bc(f1, f2, f3, filename, n);
sort_bc_to_a(f1, f2, f3, filename, n);
n *= 2;
cout << endl;
cout << "----------" << i << "----------";
Read_file(f1, filename);
Read_file(f2, "b.dat");
Read_file(f3, "c.dat");
cout << "---------------------";
cout << endl;
i++;
}
cout << endl;
cout << ":::SORTED:::" << endl;
Read_file(f1, filename);
cin.get();
}
Запустите консольное приложение и просмотрите результаты;)
добавь коментарии.
ОтветитьУдалить