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

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

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

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

1. Текст программы

#include «stdafx.h»

#include

#include

int* merge_sort (int *up, int *down, unsigned int left, unsigned int right)

{

if (left == right)

{

down[left] = up[left];

return down;

}

unsigned int middle = (unsigned int) ((left + right) * 0.5);

// разделяй и сортируй

int *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;

for (unsigned int i = left; i <= right; i++)

{

if (l_cur <= middle && r_cur <= right)

{

if (l_buff [l_cur] < r_buff [r_cur])

{

target[i] = l_buff [l_cur];

l_cur++;

}

else

{

target[i] = r_buff [r_cur];

r_cur++;

}

}

else if (l_cur <= middle)

{

target[i] = l_buff [l_cur];

l_cur++;

}

else

{

target[i] = r_buff [r_cur];

r_cur++;

}

}

return target;

}

int main ()

{

setlocale (LC_ALL, ««);

int n;

std:cout << «введите количество элементов:»;

std:cin >> n;

int* A = new int[n];

FILE* stream1;

fopen_s (&stream1, «input.txt», «r»);

for (int i = 0; i

{

fscanf_s (stream1, «%d», A + i);

}

int* c = new int[n];

A=merge_sort (A, C, 0, n-1);

FILE* stream2;

fopen_s (&stream2, «output.txt», «w»);

fprintf_s (stream2, «Результат сортировки двухпутёвым слияниемn»);

for (int i = 0; i < n; i++)

{

fprintf_s (stream2, «%d % s», A[i], ««);

}

fclose (stream1);

fclose (stream2);

return 0;

}

2. Описание программы

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 с описанием функций языка С++.

Функция 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. Описание применения

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 г., который устанавливает единые правила и порядок оформления дипломных (курсовых) проектов (работ), выполняемых студентами Тамбовского государственного технического университета и является обязательным для преподавателей и студентов университета.

Список используемых источников

1. Методы программирования: учебное пособие / Ю. Ю. Громов, О. Г. Иванова, Ю. В. Кулаков [и др.]. — Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2012. — 144 с.

2. Кулаков, Ю. В. Методы программирования [Электронный ресурс]: Программа, методические указания и задания / Ю. В. Кулаков, В. Н. Шамкин. — Тамбов: Издательство ТГТУ, 2006. — 32 с. — Режим доступа: http://window.edu.ru/window_catalog/files/r38 632/kulakov.pdf.

3. Кнут, Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы / Д. Кнут. — М.: Мир, 1976. — 736 с.

4. Макконнелл, Д. Основы современных алгоритмов / Д. Макконнелл.? М.: Техносфера, 2004.? 368 с.

5. Нивергельт, Ю. Машинный поход к решению математических задач / Ю. Нивергельт, Д. Фаррар, Э. Рейнголд.? М.: Мир, 1977.? 352 с.

6. Уайс, М. А. Организация структур данных и решение задач на C++ / М. А. Уайс.? М.: ЭКОМ Паблишерз, 2008.? 896 с.

7. Майерс, С. Эффективное использование С++. 50 рекомендаций по улучшению ваших программ и проектов / С. Майерс.? М.: ДМК Пресс; Спб.: Питер, 2006. — 240 с.

8. Стандарт предприятия. Проекты (работы) дипломные и курсовые. Правила оформления.? Тамбов: Изд-во ТГТУ, 2003.? 40 с.