Зовнішнє сортування

Міністерство  освіти і науки, молоді та спорту України

Київський національний університет будівництва і архітектури

 

 

 

Кафедра прикладної математики

 

 

 

 

 

 

ЗВІТ

до лабораторної роботи №7

з дисципліни: «Алгоритми та структури даних»

на  тему: «Зовнішнє сортування»

 

 

 

 

 

 

 

 

 

 

Виконав: студент групи ІУСТ-21

   Дарієнко А.М.

Перевірив: доц. Білощицька С.В.

 

 

 

 

 

 

 

 

 

 

Київ – 2011

 

Тема роботи: Зовнішнє сортування.

 

Мета роботи: навчитись сортувати файли даних, вміст яких перевищує об’єм оперативної пам’яті.

 

Хід роботи:

Маємо на вході файл даних «А»  з деякою кількістю невпорядкованих  чисел. Ідея методу полягає у виявленні  серій (наступний елемент має  бути більшим за попередній) при  зчитуванні із файлу «А» і запису кожної серії у «свій» файл «В» (кількість  файлів «В» – 3).

Наступний крок полягає у зчитуванні елементів серій з усіх файлів (по одному елементу кожної серії з кожного файлу «В»). Потім елементи порівнюються і записуються у файл «С». Таким чином «зливаються» всі перші серії кожного з файлів «В» і записуються у якості першої серії у файл «С1». Ті ж операції виконуються для всіх елементів наступної серії кожного з файлів «В» і «зливаються» у файл «С2» - тобто злиття серій виконується чергування файлів «С1» та «С2». І так до тих пір, поки всі серії файлів «В» не будуть «злиті» у файли «С».

Фактично повторюємо попередній крок для файлів «С» поки всі серії  не будуть впорядковано записані до кінцевого  файлу «А».

 

Блок-схема алгоритму:

 

Рис. 1. Зчитування файлу А.txt, запис у файли B1.txt, B2.txt, B3.txt.

Рис. 2. Злиття серій із файлів B1 – B3 у файли С1.txt і С2.txt.

 

Рис. 3. Злиття серій із файлів С1 – С2 у кінцевий файл A.txt.

 

Текст програми:

#include "stdafx.h"

#include <vector>

#include <fstream>

#include <iostream>

#include <conio.h>

#define N 3

 

using namespace std;

fstream fA;

 

void Create_files_b (vector<fstream> &b_file)

{

 

 

b_file[0].open("b1.txt", ios::trunc | ios::in | ios::out | ios::binary);

b_file[1].open("b2.txt", ios::trunc | ios::in | ios::out | ios::binary);

b_file[2].open("b3.txt", ios::trunc | ios::in | ios::out | ios::binary);

}

void Create_files_c (vector<fstream> &c_file)

{

c_file[0].open("c1.txt", ios::trunc | ios::in | ios::out | ios::binary);

c_file[1].open("c2.txt", ios::trunc | ios::in | ios::out | ios::binary);

}

 

void Read_A (vector<fstream> &b_file, int _x)

{

int i = 0;

int temp1, temp2;

temp1 = _x;

while(!fA.eof())

{

fA >> temp2;

 

if (temp1 < temp2)

{

b_file[i] << temp2 << " ";

}

else

{

++i;

if (i == N)

i=0;

b_file[i] << temp2 << " ";

}

 

temp1 = temp2;

}

 

}

 

int find_min (int *m, int size)

{

int min, position;

min = *(m+0);

position = 0;

for (int i = 1; i < size; i++)

if (min > *(m+i))

{

min = *(m+i);

position = i;

}

return position;

}

 

bool end_ser (vector<fstream> &file, int r, int pos)

{

ios::pos_type old_pos;

old_pos = file[pos].tellg();

int t;

file[pos] >> t;

if (r > t)

{

file[pos].seekg(old_pos);

return true;

}

else

{

file[pos].seekg(old_pos);

return false;

}

 

}

 

void sort (vector<fstream> &b_file, vector<fstream> &c_file)

{

int temp1, temp2, p, j = 0, k=0, end=0;

bool end_files[N] = {false, false, false};

int mas[N];

bool use[N] = {true, true, true};

bool end_series[N] = {false, false, false};

bool empty[N] = {true, true, true};

 

for (int i = 0; i < b_file.size(); i++)

b_file[i].seekg(ios::beg);

 

for (int i = 0; i < c_file.size(); i++)

c_file[i].seekg(ios::beg);

 

int y=0;

 

while (end != b_file.size())

{

for (int i = 0; i < b_file.size(); i++)

{

if (b_file[i].eof())

{

if(!end_files[i])

{

end++;

end_files[i] = true;

}

}

if (!use[i] || end_series[i]  || end_files[i])

continue;

b_file[i] >> mas[i];

 

if (end_ser(b_file, mas[i], i) || b_file[i].eof())

end_series[i] = true;

 

}

 

 

for (int i = 0; i < b_file.size(); i++)

if (end_series[i] || end_files[i])

k++;

 

if (k == b_file.size())

{

 

for (int i = 0; i < b_file.size(); i++)

{

p = find_min(mas, b_file.size());

if (mas[p] != 888)

{

c_file[j] << mas[p] << " ";

cout << mas[p] << " ";

}

mas[p] = 888;

}

for (int i = 0; i < b_file.size(); i++)

{

end_series[i] = false;

use[i] = true;

}

j++;

cout << endl;

 

}

else {

k = 0;

p = find_min(mas, b_file.size());

if (j == c_file.size())

j = 0;

if (mas[p] != 888)

{

empty[j] = false;

cout << mas[p] << " ";

c_file[j] << mas[p] << " ";

if (end_files[p])

mas[p]=888;

}

 

 

for (int i = 0; i < b_file.size(); i++)

{

if (p == i)

{

use[i] = true;

continue;

}

use[i] = false;

}

}

}

for (int i = 0; i < b_file.size(); i++)

{

b_file[i].close();

end_files[i] = false;

}

end = 0;

 

y=0;

for (int i = 0; i < c_file.size(); i++){

if (!empty[i])

y++;

}

if (y == 1)

return;

else

{ 

if (b_file.size() == N)

Create_files_b(b_file);

else Create_files_c(c_file);

 

sort (c_file, b_file);

}

}

 

void Destroy (vector<fstream> &b_file, vector<fstream> &c_file)

{

b_file[0].close();

b_file[1].close();

b_file[2].close();

 

c_file[0].close();

c_file[1].close();

}

 

int _tmain(int argc, _TCHAR* argv[])

{

fA.open("A.txt");

vector<fstream> b_file (N);

vector<fstream> c_file (N-1);

Create_files_b(b_file);

Create_files_c(c_file);

 

Read_A (b_file, -99);

 

sort(b_file, c_file);

Destroy(b_file, c_file);

cout << "end";

getch();

return 0;

}