4 практическая по сиаоду. СИАОД 4 практическая (Забегайлов А.Д. ИКБО-16-21) (2). Рту мирэа отчет по выполнению практического задания 4 Тема Алгоритмы внешних сортировок Выполнил студент группа икбо1619 Номер группы Москва 2022 Фамилия И. О
 Скачать 0.88 Mb.
|
|
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА Отчет по выполнению практического задания 4 Тема: Алгоритмы внешних сортировок Выполнил студент группа ИКБО-16-19 Номер группы Москва 2022 Фамилия И.О. 2 СОДЕРЖАНИЕ Задание 1 ............................................................................................................... 3 1.1 Реализация – алгоритм внешней сортировки прямого слияния к сортировке файла данных индивидуального варианта(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата): ................................. 3 1.2 Таблица результатов для файлов с увеличивающимся количеством записей (простое слияние): .............................................................................. 6 Задание 2 ............................................................................................................... 8 2.1 алгоритм внешней сортировки естественного слияния к сортировке файла данных индивидуального варианта(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата): ......................................................... 8 2.2 Таблица результатов для файлов с увеличивающимся количеством записей (естественное слияние): ................................................................... 11 Вывод: ................................................................................................................. 13 Информационные источники ............................................................................ 14 3 Задание 1 1.1 Реализация – алгоритм внешней сортировки прямого слияния к сортировке файла данных индивидуального варианта(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата): Была составлена программа алгоритма внешней сортировки прямого слияния к сортировке файла данных индивидуального варианта. Ниже представлен код функции, реализующей данный алгоритм(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата)(пример кода для 32 строчек данных): #include #include #include #include using namespace std; int main() { setlocale( LC_ALL , "RUS" ); fstream Aout; fstream Ain; fstream Bout; fstream Cout; //операции открытия файлов Aout.open( "file A.txt" , ios ::in | ios ::out); Ain.open( "file A.txt" , ofstream ::app); Bout.open( "file B.txt" , ofstream ::app); Cout.open( "file C.txt" , ofstream ::app); string a; int j = 0; int i = 1; const int bel = 32; //количество переменных int arr[bel]; int h; double del; int c = 1; for ( int i = 0; i <= 31; i++) { //присваиваение и запись значение из файла в массив arr Aout >> h; arr[i] = h; } for ( int i = 0; i <=4; i++) { //разбиение массива и распределение значения по файлам В и С del = pow(2, i); for (j = 0; j <= 31; j++) { if (c > del && c <= (del * 2)) { Cout << arr[j] << " " ; c++; } if (c <= del) { Bout << arr[j] << " " ; 4 c++; } if (c == (del * 2) + 1) c = 1; } c = 1; //операции закрытия файлов Aout.close(); Bout.close(); Cout.close(); Ain.close(); //операции открытия файлов Aout.open( "file A.txt" , ios ::in | ios ::out); Ain.open( "file A.txt" , ofstream ::app); Bout.open( "file B.txt" , ofstream ::app); Cout.open( "file C.txt" , ofstream ::app); int men = del * 2; int gi = 0; int k = 0; auto begin = chrono:: steady_clock ::now(); //Начинаем отсчёт времени при помощи chrono //сортировка прямым слиянием for ( int i = 0; i <= 32 / men; i++) { gi = gi + 1; for ( int j = 0; j <= men * gi; j++) { if (k == 0) { for ( int f = k; f < (k + men) - 1; f++) { if (arr[f] > arr[f + 1]) swap(arr[f], arr[f + 1]); } } else { for ( int f = k; f < (k + men) - 1; f++) { if (arr[f] > arr[f + 1]) swap(arr[f], arr[f + 1]); } } } k += men; } auto elapsed = chrono:: steady_clock ::now() - begin; //Заканчиваем отсчёт Ain << endl; Ain << "Время работы программы: " << ( double )chrono::duration_cast >(elapsed).count() / 1000000 << " милисекунд " << endl; //время работы программы for ( int i = 0; i <= 31; i++) { //запись отсортированного массива значений в файл Ain << arr[i] << " " ; Ain << ", 43, Тургенев, Отцы и дети, 01.06.22, 15.06.22" << endl; } if (del == 32) { //операци закрытия файлов Aout.close(); Bout.close(); Cout.close(); Ain.close(); return 0; } Bout << endl; Cout << endl; } 5 Проведём тестирование алгоритма на заданных вручную значениях (8 2 13 4 15 6 9 11 3 7 5 10 1 12 14): 6 Как мы можем видеть, алгоритм работает корректно. 1.2 Таблица результатов для файлов с увеличивающимся количеством записей (простое слияние): Таблица 1-алгоритм прямого слияния (значения6 8, 16, 32) n T(n), мс 8 0.0029 16 0.0115 32 0.0344 7 Как мы можем видеть, с учётом роста количества сортируемых значений возрастает временная сложность. Следовательно, возрастает и практическая сложность. Во всех случаях формула сложности имеет вид O(n*logn). В данном алгоритме практическая сложность равна 4 (из-за 4 циклов for). 8 Задание 2 2.1 алгоритм внешней сортировки естественного слияния к сортировке файла данных индивидуального варианта(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата): Была составлена программа алгоритма внешней сортировки естественного слияния к сортировке файла данных индивидуального варианта. Ниже представлен код функции, реализующей данный алгоритм(Учет выдачи книг пользователям библиотеки. Карточка пользователя библиотеки содержит сведения, о выданной книге: Номер читательского билета, Инвентарный номер, Автор, Название, Дата выдачи, Дата возврата)(пример кода для 8 строчек данных): #include #include #include #include using namespace std; int main() { setlocale( LC_ALL , "RUS" ); fstream Aout; fstream Ain; fstream Bout; fstream Cout; // открываем файлы Aout.open( "file A.txt" , ios ::in | ios ::out); Ain.open( "file A.txt" , ofstream ::app); Bout.open( "file B.txt" , ofstream ::app); Cout.open( "file C.txt" , ofstream ::app); char ch; string a; int j = 0; int i = 1; const int bel = 20; //количество переменных int array[bel]; int h; int del; int c = 1; for ( int i = 0; i < 4; i++) { if (i == 0) for ( int i = 0; i <= 19; i++) { //перенос значений из файла А в массив h Aout >> h; array[i] = h; } int sand = 0; 9 for ( int i = 0; i <= 19; i++) { //перенос значений из массива h в файлы B и C, cогласно их значению относительно стоящего справа значения if ((array[i] < array[i + 1]) && (sand % 2 != 0)) Bout << array[i] << " " ; if ((array[i] < array[i + 1]) && (sand % 2 == 0)) Cout << array[i] << " " ; if (array[i] > array[i + 1] or (array[i] == array[i + 1])) { if (sand % 2 != 0) Bout << array[i] << " " ; if (sand % 2 == 0) Cout << array[i] << " " ; sand = sand + 1; } } sand = 0; int kast = 0; int start; int ystart = 0; Ain << endl; auto begin = chrono:: steady_clock ::now(); //Начинаем отсчёт времени при помощи chrono for ( int i = 0; i <= 19; i++) { //сортировка естественным слиянием if (array[i] < array[i + 1] && ystart == 0) { start = i; } ystart++; if (array[i] > array[i + 1] && (i < 19)) kast++; if (i + 1 == 20) kast++; if (kast % 2 == 0 && kast != 0) { for ( int j = start; j <= i - 1; j++) { for ( int k = start; k < i; k++) { if (array[k] > array[k + 1]) swap(array[k], array[k + 1]); } } start = 0; kast = 0; ystart = 0; } } auto elapsed = chrono:: steady_clock ::now() - begin; //Заканчиваем отсчёт Ain << "Время работы программы: " << ( double )chrono::duration_cast >(elapsed).count() / 1000000 << " милисекунд " << endl; //время работы программы for ( int i = 0; i <= 19; i++) { //переправка в файл отсортированных значений из массива Ain << array[i] << " " ; Ain << ", 43, Тургенев, Отцы и дети, 01.06.22, 15.06.22" << endl; } Bout << endl; Cout << endl; int sell = 0; for ( int i = 0; i < 19; i++) { //проверка массива на необходимость дальнейшей сортировки if (array[i] > array[i + 1]) sell = sell + 1; } if (sell == 0) //при условии успеха сортировки закончить выполнение программы return 0; 10 } return 0; } Проведём тестирование алгоритма на заданных вручную значениях (17 31 5 59 13 41 43 67 11 23 29 47 3 7 71 2 19 57 37 61): 11 Как мы можем видеть, алгоритм работает корректно. 2.2 Таблица результатов для файлов с увеличивающимся количеством записей (естественное слияние): Таблица 2-алгоритм естественного слияния (значения 8, 16, 32) n T(n), мс 8 0.0019 16 0.0034 32 0.0311 12 13 Вывод: По результатам проведённых тестов мы приходим к следующему выводу: Алгоритм сортировки файла естественным слиянием (алгоритм 2) эффективнее алгоритма сортировки файла прямым слиянием (алгоритм 1). 14 Информационные источники 1. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона, 2010. 2. Кнут Д. Искусство программирования. Тома 1-4, 1976-2013. 3. Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих, 2017. 4. Кормен Т.Х. и др. Алгоритмы. Построение и анализ, 2013. 5. Лафоре Р. Структуры данных и алгоритмы в Java. 2-е изд., 2013. 6. Макконнелл Дж. Основы современных алгоритмов. Активный обучающий метод. 3-е доп. изд., 2018. 7. Скиена С. Алгоритмы. Руководство по разработке, 2011. 8. Хайнеман Д. и др. Алгоритмы. Справочник с примерами на C, C++, Java и Python, 2017. 9. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология, 2003. |