Сортировка слиянием

Сортировка слиянием

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Тульский государственный педагогический университет им. Л.Н.Толстого»

(ФГБОУ ВПО «ТГПУ им. Л.Н. Толстого »)

Кафедра информатики и информационных технологий

КУРСОВАЯ РАБОТА

по дисциплине «Основы программирования»

на тему:

«Сортировка слиянием»

Выполнил:

студент 2 курса группы 121131

факультета Математики, Физики и Информатики

направления «Фундаментальная информатика и информационные системы»

профиля «Открытые информационные системы»

Чурилов Александр Викторович

Научный руководитель:

доцент, к.п.н.,

Якушин А.В.

Тула-2015

Содержание

Введение

Глава 1. Алгоритм сортировки слиянием

.1 Постановка задачи сортировки

.2 Алгоритм сортировки простым слиянием

.3 Алгоритм сортировки естественным слиянием

.4 Оценка сложности алгоритма

Глава 2. Реализация алгоритмов сортировки слияниями

.1 Программная реализация простого слияния

.2 Программная реализация естественного слияния

Глава 3. Тестирование

.1 Тестирование меню на корректность входных данных

Список использованной литературы

Приложения

Приложение 1

Приложение 2

Введение

Необходимость отсортировать какие-либо величины возникает в программировании довольно часто. К примеру, входные данные подаются «вперемешку», а программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.

Сколь бы хорошими и эффективными не был выбранный вами алгоритм, но если в качестве подзадачи он использует «плохую» сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом.

Данная курсовая работа посвящена рассмотрению одного из важных методов сортировки данных - сортировке методом слияний. Сортировка методом слияний является одним из наиболее известных алгоритмов внешних сортировок - сортировок, требующих для работы внешней памяти компьютера.

Данные, хранящиеся на внешних устройствах, имеют больший объём, что не позволяет их целиком переместить в оперативную память, отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их во внешнее устройство.

Цель данной курсовой работы: рассмотрение алгоритмов сортировок методом слиянием.

В ходе этой курсовой работы рассмотрены следующие вопросы:

понятие сортировки и алгоритма сортировки;

критерии оценивания алгоритмов сортировок;

классификация алгоритмов сортировок;

рассмотрение и анализ основных понятий сортировок слияниями;

описание общей схемы слияний;

описание методов простого и естественного слияний;

описание программ, реализующих алгоритмы сортировки простым слиянием и естественным слиянием.

Для демонстрации данных алгоритмов выбран С++ - высокоуровневый и современный язык программирования, предназначенный для решения широкого класса задач. Эти алгоритмы рассмотрены в среде программирования Microsoft Visual Studio 2010.

Глава 1. Алгоритм сортировки слиянием

Алгоритм сортировки слияниями был изобретён венгеро-американским математиком Джоном фон Нейманом в 1945 году. Он является одним из самых быстрых способов сортировки.

Слияние - это объединение двух или более упорядоченных массивов в один упорядоченный.

Сортировка слияниями является одним из самых простых алгоритмов сортировки (среди быстрых алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске). Кроме того, сортировка слиянием является алгоритмом, который может быть эффективно использован для сортировки таких структур данных, как связанные списки.

Данный алгоритм применяется тогда, когда есть возможность использовать для хранения промежуточных результатов память, сравнимую с размером исходного массива. Он построен на принципе «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Далее их решения комбинируются, и получается решение исходной задачи.

Процедура слияния требует два отсортированных массива. Заметим, что массив из одного элемента по определению является отсортированным.

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

Фаза - это последовательность действий, необходимых для однократной обработки всех элементов.

Проход - это наименьший процесс, реализация которого составляет алгоритм сортировки.

Двухфазная сортировка - это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка - это сортировка, в которой объединены фазы распределения и слияния в одну.

Исходные данные разбиваются на серии, или упорядоченные отрезки, и распределяются на два и более вспомогательных массива. Это распределение идет поочередно: первая серия записывается в первый вспомогательный массив, вторая - во второй и т.д. После того, как произошла запись серии в последний вспомогательный массив, следующая по счёту серия записывается опять в первый вспомогательный массив. После распределения всех серий они объединяются в более длинные упорядоченные отрезки: из каждого вспомогательного массива берется по одной серии, и серии сливаются. Если в каком-то массиве серия заканчиваются, то следующая серия пока не рассматривается. Сформированный более длинный упорядоченный отрезок записывается либо в исходный массив, либо в какой-то из вспомогательных. Далее происходит распределение этих длинных серий во вспомогательные массивы с последующим их слиянием. До тех пор пока все данные не будут упорядочены.

В сортировке слияниями выделяют две основные характеристики:

)        Количество вспомогательных массивов. В случае если вспомогательных массивов два, распределение называется двухпутевым, а вся сортировка - двухпутевым слиянием.

)        Количество фаз (шагов, этапов) в реализации сортировки.

Алгоритм сортировки слияниями

Шаг 1. Разбить имеющиеся элементы массива на пары и осуществить слияние элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть может, одного элемента, для которого не нашлось пары).

Шаг 2. Разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары.

Шаг 3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

.1 Постановка задачи сортировки

алгоритм слияние сортировка простой

Сортировка является важнейшей задачей программирования. Для её решения разработано множество различных алгоритмов. В общем случае под сортировкой следует понимать процесс расставления заданного множества объектов в определённом порядке.

Алгоритм сортировки - это алгоритм для упорядочивания некоторого множества элементов. Чаще всего упорядочивание происходит по возрастанию или по убыванию. Алгоритмы сортировки находят широкое применение в различных областях программирования: начиная от работы с огромными объёмами баз данных, заканчивая составлением программ для решения математических задач.

Задачи, связанные с обработкой данных, решаются намного проще, если множество данных заранее упорядочено.

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

В алгоритмах сортировки часть данных используется в качестве ключа сортировки - атрибута (или нескольких атрибутов), по значению которого определяется порядок элементов. При написании алгоритмов сортировок массивов всегда следует учесть, что ключ полностью или частично совпадает с данными.

Оценка алгоритмов проводится по следующим параметрам:

·        Время сортировки - быстродействие алгоритма.

·        Память - характеристика для временного хранения данных во время выполнения алгоритма.

·        Устойчивость - неизменность взаимного расположения элементов с равными значениями.

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

Выделяют алгоритмы внутренней и внешней сортировок. В первом случае для временного хранения данных используется лишь оперативная память компьютера. Во втором случае алгоритм сортировки использует внешнюю память компьютера (как правило, жёсткие диски). Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память. Нелишним будет отметить, что алгоритмы внутренней сортировки значительно эффективнее алгоритмов внешней : на обращение к внутренней памяти компьютера затрачивается намного меньше времени, чем к внешней. Если в какой-либо задаче имеется возможность записать данные из внешней памяти в оперативную, то лучше воспользоваться этой возможностью, и перейти от внешних сортировок к внутренним.

.2 Алгоритм сортировки простым слиянием

На первом проходе сортируются пары соседних элементов исходного массива. Затем осуществляется слияние соседних пар, после этого четвёрок, восьмёрок и т.д. Трудоёмкость такого метода в общем случае определяется по формуле n * log2 n, однако данную сортировку достаточно сложно реализовать, не задействовав дополнительную память, поэтому сортировку слияниями следует использовать тогда, когда количество элементов массива сопоставимо с задействованными ресурсами дополнительной памяти.

Пример. Исходный массив:

         -2      0       -6      3       1       -5

Сортировка простым слиянием заканчивается если:

)после фазы слияния длина серии не меньше количества элементов в массиве;

)на фазе слияния осталась ровно одна серия;

)второй по счёту вспомогательный массив для однофазной сортировки остался пустым.

//Описание функции сортировки простым слиянием

void p_sort(int *Mas, int first, int last)

{

{(first<last)

{_sort(Mas, first, (first+last)/2);

//сортировка левой части_sort(Mas, (first+last)/2+1, last);

//сортировка правой части_mass(Mas, first, last);

//слияние двух частей

}

}

}

Листинг 1.Алгоритм сортировки простым слиянием

.3 Алгоритм сортировки естественным слиянием

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

3 14 | 6 8 9 | 2 4 5 7 11 | 10 16

Естественное слияние заканчивается тогда, когда:

)на фазе слияния осталась ровно одна серия;

)второй по счёту вспомогательный массив для однофазной сортировки после распределения серии остался пустым.

Естественное слияние может оказаться несбалансированным. Это произойдёт в том случае, если количество серий, записанных во вспомогательные массивы, будет существенно отличаться друг от друга.

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

//Описание функции сортировки естественным слиянием

void sort (int q, int x[])

{k1, k2, st, u, fl;* tm1 = new int[q];

// временный массив 1* tm2 = new int[q];

// временный массив 2

int pos;

k1=0;

std::sort(x, x + q - 1);

{=1;=1;=0;(fl==1)

{=0; ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) // выбираем возрастающие цепочки элементов.

{[u]=x[u+st-1];++;

}((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{[u]=x[u+st-1]; u++;

}=u;=st+k1;=0;((x[u+st-1]<=x[u+st]) &&(u+st-1 < q))

// аналогичным образом формируем второй массив

{

tm2[u]=x[u+st-1];++;

}((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))

{[u]=x[u+st-1]; u++;

}=u;=st+k2;(u > 0)(k1, k2, tm1, tm2, x);

// сливаем эти два массива в один

if (st >= q) fl=0;

}

}[] tm1;

delete [] tm2;

Листинг 2.Алгоритм сортировки естественным слиянием

1.4 Оценка сложности алгоритма

Единственного эффективнейшего алгоритма сортировки нет, ввиду множества параметров оценки эффективности:

1) Время - основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью <#"871515.files/image002.jpg">

Выбираем пункт меню 2:

Выбираем пункт меню 3:

Выбираем пункт меню 3:

Выбираем пункт меню 5:

Выбираем пункт меню -1:

Приложение 2

Результат выполнения программы сортировки простым слиянием

Результат выполнения программы сортировки естественным слиянием