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

Общее описание и структура программы, ее компоненты и функции, сферы практического применения. Требования к функциональным возможностям. Характеристика логической структуры, используемые технические средства. Исследование входных и выходных данных.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 30.01.2016
Размер файла 94,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

#include «stdafx.h»

#include <iostream>

#include <cstdlib>

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<n; 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. [Найти наименьший элемент.] Если 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. Описание применения

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 с.

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

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

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

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

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

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

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

Размещено на Allbest.ru


Подобные документы

  • Назначение и область применения, технические характеристики, постановка задачи, описание алгоритма и организация входных и выходных данных для программы. Разработка, описание логической структуры, используемые технические средства и условия выполнения.

    курсовая работа [969,3 K], добавлен 26.03.2009

  • Основания для разработки программы: назначение и сферы практического использования, главные предъявляемые требования. Характеристика логической структуры и используемые технические средства. Программа и методика испытаний. Эксплуатационные документы.

    курсовая работа [2,4 M], добавлен 16.12.2013

  • Разработка эскизного и технического проектов программы, ее назначение и область применения, технические характеристики. Организация входных и выходных данных, выбор состава технических и программных средств. Текст программы, ее описание и тестирование.

    курсовая работа [1,3 M], добавлен 15.11.2009

  • Комбинированный тип данных для хранения входных данных о студентах и информация, содержащаяся в полях. Пример структуры входных и выходных данных. Алгоритм работы и программный код программы по успеваемости студентов, описание используемых функций.

    курсовая работа [135,9 K], добавлен 28.12.2012

  • Разработка эскизного и технического проектов программы, ее назначение и область применения, описание алгоритма, организация входных и выходных данных. Выбор состава технических и программных средств, разработка рабочего проекта, спецификация программы.

    курсовая работа [159,8 K], добавлен 26.01.2010

  • Назначение и область применения программы, ее общее описание, функциональные особенности и задачи, логистическая структура, используемые технические средства. Создание руководства оператора. Расчет технико-экономических показателей создаваемой программы.

    курсовая работа [1,2 M], добавлен 09.11.2013

  • Область применения – учебные учреждения, где ведется учет пропусков занятий студентами. Технические характеристики разрабатываемого проекта: описание основных типов входных и выходных данных, алгоритм программы. Технико-экономические показатели проекта.

    курсовая работа [906,3 K], добавлен 28.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.