Разработка программы сортировки двухпутевым слиянием по алгоритму М
Введение
Алгоритм сортировки двухпутевым
слиянием используется для получения отсортированного массива данных.
Если разница между количеством
элементов в двух исходных массивах не слишком велика, то данный вид сортировки
будет, пожалуй, наилучшим. В противном же случае, выгоднее будет использовать
более эффективные алгоритмы. Под сортировкой двухпутевым слиянием понимается
сортирование исходного массива с помощью его разбивания на несколько частей, а
потом их слияния с помощью алгоритма М.
Общий объём работы, выполняемой
алгоритмом М, по существу, пропорционален сумме количества элементов в
двух исходных файлах.
1. Текст программы
#include «stdafx.h»
#include
<iostream>
#include <cstdlib>
int* merge_sort (int
*up, int *down, unsigned int left, unsigned int right)
{
(left == right)
{[left] = up[left];down;
}
int middle = (unsigned
int) ((left + right) * 0.5);
// разделяй и
сортируй*l_buff = merge_sort (up, down, left, middle);
int *r_buff =
merge_sort (up, down, middle + 1, right);
// слияние двух отсортированных
половин
int *target = l_buff == up? down: up;
unsigned int width =
right - left, l_cur = left, r_cur = middle + 1;(unsigned int i = left; i <=
right; i++)
{(l_cur <= middle
&& r_cur <= right)
{(l_buff [l_cur] <
r_buff [r_cur])
{[i] = l_buff [l_cur];_cur++;
}
{[i] = r_buff
[r_cur];_cur++;
}
}if (l_cur <= middle)
{
target[i]
= l_buff [l_cur];_cur++;
}
{[i] = r_buff
[r_cur];_cur++;
}
}target;
}
main()
{(LC_ALL, «»);n;:cout << «введите количество элементов:»;
std:cin >> n;* A =
new int[n];* stream1;_s (&stream1, «input.txt», «r»);(int i = 0; i<n;
i++)
{
fscanf_s
(stream1, «%d», A + i);
}* c = new
int[n];=merge_sort (A, C, 0, n-1);* stream2;_s (&stream2, «output.txt»,
«w»);_s (stream2, «Результат сортировки двухпутёвым слиянием\n»);
for (int i = 0; i <
n; i++)
{_s (stream2, «%d % s»,
A[i], «»);
}(stream1);(stream2);0;
}
2. Описание программы
.1 Общие сведения
Программа M_sli «Сортировка двухпутевым
слиянием» написана на языке C++. Для функционирования
программы необходима операционная система Microsoft Windows XP и выше.
2.2 Функциональное
назначение
Программа сортировки двухпутевым
слиянием используется для получения отсортированного массива данных.
2.3 Описание логической
структуры
Этот алгоритм читает массив
последовательно из входного файла и записывает в выходной файл отсортированный
массив, получившийся после выполнения сортировки.
Имеется один массив с входными
данными, имеющий m элементов.
A - указатель на первый
элемент массива с входными данными;
C - указатель на массив,
использующийся как буфер;
up - указатель на массив,
который нужно сортировать;
down - указатель на массив С,
использующийся как буфер;
left - левая граница массива;
right - правая граница
массива;
middle - середина массива, для которого вызывается функция сортировки;
target - указатель на отсортированный массив, возвращаемый функцией;
Программа реализует алгоритм M сортировки двухпутевым
слиянием [1, 2]:
M1. [Начальная установка.] Установить i ← 1, j ← 1, k ← 1.
M2. [Найти наименьший элемент.] Если xi≤yj, то перейти к шагу
M3;
в противном случае к шагу М5.
M3. [Вывести xi.] Установить zk← xi, k← k+1, i← i+1. Если i≤m, то вернуться к шагу M2.
M4. [Вывести yj, …, yn.]
Установить (zk,…, zm+n)← (yj,…, yn) и
завершить работу алгоритма.
M5. [Вывести xi.] Установить zk← yj, k← k+1, j← j+1. Если j≤n, то вернуться к шагу M2.
M6. [Вывести xi, …, xm.]
Установить (zk,…, zm+n)← (xi,…,
xm) и завершить работу алгоритма. ■
Программа содержит директивы #include и главную функцию main.
Директивы #include вставляют в код
программы файлы stdafx.h, и cstdlib с описанием стандартных функций языка C, iostream с описанием функций
языка С++ [7].
Функция main формирует ввод из input.txt исходного массива с
данными и вывод в output.txt отсортированного массива, полученного в результате выполнения
алгоритма.
2.4 Используемые
технические средства
PC-совместимый компьютер следующей минимальной конфигурации:
процессор с тактовой частотой не ниже 800 МГц и объемом оперативной памяти не
ниже 512 Мбайт.
2.5 Вызов и загрузка
Вызов осуществляется запуском файла
программы M_sli.exe, а загрузка из файла input.txt. Файлы M_sli.exe, input.txt хранятся в прилагаемом сменном оптическом носителя типа CD-R.
2.6 Входные данные
Входным данным программы является
массив из n элементов, он находится в файле input.txt.
2.7 Выходные данные
Выходным данным является
отсортированный массив, он будет находиться в файле output.txt. Файл output.txt автоматически создается
после запуска исполняемого файла программы M_sli.exe на прилагаемом сменном
оптическом носителя типа CD-R.
3. Описание применения
.1 Назначение программы
Программа предназначена для
проведения сортировки двухпутёвым слиянием.
3.2 Условия применения
Для выполнения программы необходим PC-совместимый компьютер с
процессором тактовой частоты не ниже 800 МГц и объемом оперативной памяти не
ниже 512 Мбайт, с установленной операционной системой Microsoft Windows XP и выше.
Входным данным программы является
массив, его мы загружаем из файла input.txt.
Выходным данным является
отсортированный по возрастанию массив, который будет сохраняться в файле output.txt.
3.3 Описание задачи
Технология сортировки двухпутёвым
слиянием представляет прекрасный способ прекрасный пример реализации принципа
«разделяй и властвуй». Сначала задача разбивается на несколько подзадач
меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или
непосредственно, если их размер достаточно мал. После этого их решения
комбинируются и получается решение исходной задачи.
Данная программа поддерживает
сортировку только целых чисел.
3.4 Входные и выходные
данные
Входным данным программы является
массив, который находится в файле input.txt.
Выходным данным является
отсортированный массив, он будет находиться в файле output.txt.
4. Тестовый пример
Массив из четырнадцати элементов
находится в файле input.txt, снимок этого файла
изображен на рисунке 1.
Успешное прохождение программой M_sli.exe этого теста
подтверждают снимки экрана, изображённые на рисунке 2 и рисунке 3.
Рисунок 1 - Содержание файла input.txt
Рисунок 2 - Результат выполнения
программы
программа логический технический
Рисунок 3 - Содержание файла output.txt
Заключение
Разработана программа M_sli.exe сортировки двухпутевым слиянием.
Тестирование программы подтвердило её работоспособность.
Работа оформлена в соответствии со
стандартом предприятия СТП ТГТУ 07-97, введенным с 1 января 1998 г., который
устанавливает единые правила и порядок оформления дипломных (курсовых) проектов
(работ), выполняемых студентами Тамбовского государственного технического
университета и является обязательным для преподавателей и студентов
университета [8].
Список используемых
источников
1. Методы программирования: учебное пособие / Ю.Ю. Громов, О.Г.
Иванова, Ю.В. Кулаков [и др.]. - Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2012. - 144
с.
. Кулаков, Ю.В. Методы программирования [Электронный ресурс]:
Программа, методические указания и задания / Ю.В. Кулаков, В.Н. Шамкин. -
Тамбов: Издательство ТГТУ, 2006. - 32 с. - Режим доступа: http://window.edu.ru/window_catalog/files/r38632/kulakov.pdf.
3. Кнут, Д. Искусство программирования для ЭВМ. Т. 1. Основные
алгоритмы / Д. Кнут. - М.: Мир, 1976. - 736 с.
. Макконнелл, Д. Основы современных алгоритмов / Д. Макконнелл. −
М.: Техносфера, 2004. − 368 с.
5. Нивергельт, Ю. Машинный поход к решению математических задач /
Ю. Нивергельт, Д. Фаррар, Э. Рейнголд. − М.: Мир, 1977. − 352 с.
. Уайс, М.А. Организация структур данных и решение задач на C++ / М.А. Уайс. − М.: ЭКОМ Паблишерз,
2008. − 896 с.
. Майерс, С. Эффективное использование С++. 50 рекомендаций по
улучшению ваших программ и проектов / С. Майерс. − М.: ДМК Пресс; Спб.:
Питер, 2006. - 240 с.
8. Стандарт предприятия. Проекты (работы) дипломные и курсовые.
Правила оформления. − Тамбов: Изд-во ТГТУ, 2003. − 40 с.