Разработка программы сортировки двухпутевым слиянием по алгоритму М

Разработка программы сортировки двухпутевым слиянием по алгоритму М

Введение

Алгоритм сортировки двухпутевым слиянием используется для получения отсортированного массива данных.

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

Общий объём работы, выполняемой алгоритмом М, по существу, пропорционален сумме количества элементов в двух исходных файлах.

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. [Найти наименьший элемент.] Если x_i≤y_j, то перейти к шагу M3; в противном случае к шагу М5.

M3. [Вывести x_i.] Установить z_k← x_i, k← k+1, i← i+1. Если i≤m, то вернуться к шагу M2.

M4. [Вывести y_j, …, y_n.] Установить (z_k,_…, z_m+n)← (y_j,_…, y_n) и завершить работу алгоритма.

M5. [Вывести x_i.] Установить z_k← y_j, k← k+1, j← j+1. Если j≤n, то вернуться к шагу M2.

M6. [Вывести x_i, …, x_m.] Установить (z_k,_…, z_m+n)← (x_i,_…, x_m) и завершить работу алгоритма. ■

Программа содержит директивы #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 с.