Преподаватель который помогает студентам и школьникам в учёбе.

Анализ алгоритмов сортировок методом слияния

Содержание:

Введение

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

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

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

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

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

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

Понятие сортировки и алгоритма сортировки;
Критерии оценивания алгоритмов сортировок;
Классификация алгоритмов сортировок;
Рассмотрение и анализ основных понятий сортировок слияниями;
Описание общей схемы слияний;
Описание методов простого и естественного слияний;
Описание программ, реализующих алгоритмы сортировки простым слиянием и естественным слиянием.

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

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

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

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

Несколько детально этот процесс можно расписать так:

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

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

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

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

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

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

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

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

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

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

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

Количество вспомогательных массивов. В случае если вспомогательных массивов два, распределение называется двух путевым, а вся сортировка – двух путевым слиянием.
Количество фаз (шагов, этапов) в реализации сортировки.

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

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

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

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

Демонстрация сортировки слиянием по возрастанию представлена на рисунке 1.

Рис.1. Демонстрация сортировки слиянием по возрастанию

Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.

Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

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

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

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

Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла.Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

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

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

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

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

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

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

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

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

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

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

Одна из сортировок на основе слияния называется простым слиянием.

Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.

В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -гошага – 2k.

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

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

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

После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.

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

Длина серии не меньше количества элементов в файле (определяется после фазы слияния);
Количество серий равно 1 (определяется на фазе слияния).
При однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.

Пример продемонстрирован ниже

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

7 -2 0 -6 3 1 -5

№ прохода	Распределение	Слияние
1	М1: 7 0 3 -5 М2: -2 -6 1	-2 7 -6 0 1 3 -5
2	М1: -2 7 1 3 М2: -6 0 -5	-6 -2 0 7 -5 1 3
3	М1: -6 -2 0 7 М2: -5 1 3	-6 -5 -2 0 1 3 7

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

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

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

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

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

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

{

if (first<last)

{

p_sort(Mas, first, (first+last)/2);

//сортировка левой части

p_sort(Mas, (first+last)/2+1, last);

//сортировка правой части

sliv_mass(Mas, first, last);

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

}

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

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

При использовании метода прямого слияния не принимается во внимание то, что исходный файл может быть частично отсортированным, т.е. содержать упорядоченные подпоследовательности записей. Серией называется подпоследовательность записей ai, a(i+1), ..., aj такая, что ak <= a(k+1) для всех i <= k < j, ai < a(i-1) и aj > a(j+1). Метод естественного слияния основывается на распознавании серий при распределении и их использовании при последующем слиянии.

Как и в случае прямого слияния, сортировка выполняется за несколько шагов, в каждом из которых сначала выполняется распределение файла A по файлам B и C, а потом слияние B и C в файл A. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла A. Процесс завершается, когда в файле A остается только одна серия. Пример сортировки файла показан на рисунках 2 и 3.

Рис. 2 Первый шаг

Рис. 3 Второй шаг

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

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

№ прохода

Распределение

Слияние

М1: 1 3 14 2 4 5 7 11

М2: 6 8 9 10 16

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

М1: 1 3 6 8 9 14

М2: 2 4 5 7 10 11 16

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

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

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

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

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

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

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

void sort (int q, int x[])

{

int k1, k2, st, u, fl;

int* tm1 = new int[q];

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

int* tm2 = new int[q];

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

int pos;

k1=0;

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

while (k1 < q-1)

{

st=1;

fl=1;

pos=0;

while (fl==1)

{

u=0;

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

{

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

u++;

}

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

{

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

}

k1=u;

st=st+k1;

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q))

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

{

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

u++;

}

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

{

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

}

k2=u;

st=st+k2;

if (u > 0)

merge(k1, k2, tm1, tm2, x);

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

if (st >= q) fl=0;

}

delete [] tm1;

delete [] tm2;

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

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

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

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

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

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

#include <stdio.h>

#include <iostream>

using namespace std;

void sliv_mass(int *Mas, int first, int last) //функция, сливающая массивы

{

int middle, start, final, j;//переменные целого типа

int *mas=new int[100];// описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new:

middle=(first+last)/2; //вычисление среднего элемента

start=first;//начало левой части

final=middle+1;//начало правой части

for(j=first; j<=last; j++)//выполнять от начала до конца

if ((start<=middle)&&((final>last) || (Mas[start]<Mas[final])))

{

mas[j]=Mas[start];

start++;//увеличить start на 1

}

else

{

mas[j]=Mas[final];

final++;//увеличить final на 1

}

for (j=first; j<=last; j++)

Mas[j]=mas[j];//возвращение результата в список

delete[]mas;

};

void p_sort(int *Mas, int first, int last)//рекурсивная процедура сортировки

{

if (first<last)

{

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

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

sliv_mass(Mas, first, last);//слияние двух частей

}

void main()//главная функция

{

setlocale(LC_ALL, "Rus");

int i, n;

int *Mas=new int[100];

cout<<"Введите размер массива: ";

cin>>n;//вводим n с клавиатуры

for (i=1; i<=n; i++)

{

cout<<i<<" элемент: ";

cin>>Mas[i];

}

p_sort(Mas, 1, n);//вызов сортирующей процедуры

cout<<"Упорядоченный массив: ";//вывод упорядоченного массива

for (i=1; i<=n; i++)

cout<<Mas[i]<<" ";

delete []Mas;//освобождение памяти

system("pause");

}

Листинг 3. Исходный код модуля простое слияние.cpp

Скриншот данной программы приведен в приложении 2.

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

#include <stdlib.h>

#include <iostream>

#include <stdio.h>

#include <time.h>

#include <algorithm>

#include <fstream>//подключаем библиотеку для работы с файлами

using namespace std;

int size=5;

ifstream r;

void merge(int k1, int k2, int *mass1, int *mass2, int *x) // слияние 2 массивов

{

int z1 = 0; int z2 = 0; int i;// счетчики позиций на временных массивах и в результирующем

for (unsigned int i = 0; i < k1 + k2; ++i)

{

if (z1 >= k1)

{

x[i] = mass2[z2++]; // сливаем по возрастанию элементов

} else if (z2 >= k2) {

x[i] = mass1[z1++];

} else {

if (mass1[z1] <= mass2[z2]) {

x[i] = mass1[z1++];

} else {

x[i] = mass2[z2++];

}

void sort (int q, int x[])

{

int k1, k2, st, u, fl;

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

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

int pos;

k1=0;

sort(x, x + q - 1);

while (k1 < q-1)

{

st=1;

fl=1;

pos=0;

while (fl==1)

{

u=0;

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

{

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

u++;

}

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

{

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

}

k1=u;

st=st+k1;

u=0;

while ((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) // аналогичным образом формируем второй массив

{

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

u++;

}

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

{

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

}

k2=u;

st=st+k2;

if (u > 0)

merge(k1, k2, tm1, tm2, x); // сливаем эти два массива в один

if (st >= q) fl=0;

}

delete [] tm1;

delete [] tm2;

}

int main()

{

setlocale(LC_ALL, "RUS");

cout<<"Размерность массива = "<<size<<endl;

int *x = new int [size];

int i;

r.open("D:\111\Естественное слияние\Естественное слияние\fail.txt");//открыли файл

cout<<"Исходный массив: ";

for (i = 0; i < size; ++i)

{

r>>x[i];

}

for (i = 0; i < size; ++i)

{

cout<<x[i]<<" ";

}

sort(size, x); // сортируем

cout<<endl;

cout<<"Отсортированный массив: ";

for (i = 0; i < size; ++i)

{

cout<<x[i]<<" ";

}// и ещё раз выводим

cout<<endl;

system("pause");

r.close();//закрыли файл

return 0;

}

Листинг 3. Исходный код модуля естественное слияние.cpp

Скриншот данной программы приведен в приложении 2.

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

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

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

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

Существует несколько признаков, по которым принято производить классификацию видов тестирования. Обычно выделяют следующие:

По объекту тестирования:

Функциональное тестирование;
Тестирование производительности;
Юзабилити-тестирование;
Тестирование интерфейса пользователя;
Тестирование безопасности;
Тестирование локализации;
Тестирование совместимости.

По знанию системы:

Тестирование чёрного ящика;
Тестирование белого ящика;
Тестирование серого ящика

По степени автоматизации:

Ручное тестирование;
Автоматизированное тестирование;
Полуавтоматизированное тестирование.

По степени изолированности компонентов:

Компонентное (модульное) тестирование;
Интеграционное тестирование;
Системное тестирование.

По времени проведения тестирования:

Альфа-тестирование;
Бета-тестирование.

По признаку позитивности сценариев:

Позитивное тестирование;
Негативное тестирование.

По степени подготовленности к тестированию:

Тестирование по документации;
Тестирование ad hoc или интуитивное тестирование.

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

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

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

Данный вид пригодится при сравнении алгоритмов и выявлении наименее затратного по времени.

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

Таблица 1. Результаты корректности входных данных

n	Ожидаемый результат	Фактический результат
1	Выбирает первый пункт меню «О программе»	Выбирает первый пункт меню «О программе»
2	Выбирает второй пункт меню «Об авторе»	Выбирает второй пункт меню «Об авторе»
3	Выбирает третий пункт меню «Сортировка простым слиянием»	Выбирает третий пункт меню «Сортировка простым слиянием»
0	Выходит из программы	Закрывает консоль
n>5	Такого пункта меню нет, функция снова вызовет меню и попросит ввести корректное значение	Функция выдает пользователю, что такого пункта меню нет, и снова запрашивает ввод значения
4	Выбирает четвертый пункт меню «Сортировка естественным слиянием»	Выбирает четвертый пункт меню «Сортировка естественным слиянием»
n<0	Такого пункта меню нет, функция снова вызовет меню и попросит ввести корректное значение	Функция выдает пользователю, что такого пункта меню нет, и снова запрашивает ввод значения
символ	Символ не является целочисленным элементом, программа попросит ввести корректное значение	Функция выдает пользователю, что такого пункта меню нет, и снова запрашивает ввод значения
строка	Строка не является целочисленным элементом, программа попросит ввести корректное значение	Функция выдает пользователю, что такого пункта меню нет, и снова запрашивает ввод значения

Вывод: программа работает корректно, поскольку рассмотрены все случаи ввода пункта меню, при которых программа бы выдавала ошибку или происходил бы ее сбой.

Заключение

В ходе данной курсовой работы были рассмотрены вопросы, связанные с сортировкой данных методом слияний. Были рассмотрены и проанализированы основные понятия сортировок слияниями: серия, фаза, слияние, простое слияние, естественное слияние. Была описана общая схема слияний и дано её описание на простом примере. Также был разработан и подробным образом рассмотрен код программы, реализующей алгоритмы сортировок методом простого и естественного слияния.

Заданная цель и поставленные цели в полной мере были реализованы. Метод сортировок слияниями является алгоритмом внешней сортировки данных, и потому применяется лишь при обработке огромных массивов информации (баз данных и пр.). Данные методы могут быть усовершенствованы в ходе основных критериев, рассмотренных в курсовой работе: памяти, естественности, времени и устойчивости.

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

Мальцев А. И., Алгоритмы и рекурсивные функции, — 2-е издание, 1986.
Окулов С. М., Программирование в алгоритмах, М.: БИНОМ. Лаборатория знаний, 2002.
Подбельский, В.В. Программирование на языке Си: учеб.пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004.
Подбельский, В.В. Язык Си++: учеб.пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005.
Седжвик Роберт, Фундаментальные алгоритмы на С++. Анализ/ структуры данных/ сортировка/ поиск, 2001.
Сундукова, Т.О., Ваныкина, Г.В.. Структуры и алгоритмы компьютерной обработки данных [Электронный ресурс]: INTUIT.RU: Учебный курс — Структуры и алгоритмы компьютерной обработки данных / Интернет-Университет Информационных технологий. — 2006.
Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие / Б.С. Хусаинов. – М.: Финансы и статистика, 2004.
Ахо Альфред В. Структуры данных и алгоритмы: Вильямс / пер. с английского и ред. Минько А. А., Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. — М. и др.: Вильямс, 2001. – 382 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999. – 960 с.
Кнут Д.Э. Искусство программирования: в 3-x томах. — 2-е издание. – М.: Мир, 1976 – 1978 .(3-е изд.: Вильямс, 2010)
Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Издательский дом «Вильямс», 2006. – 576 с.
Макконнелл Дж. Основы современных алгоритмов. 2-е изд., доп. – М.: Техносфера, 2004. – 368 с.
Макконелл, Дж. Анализ алгоритмов. Вводный курс / Дж. Макконелл,- М.: Техно-сфера, 2002,- 304 с.
Вирт Никлаус Алгоритмы и структуры данных: Нев. Диалект / Вирт Никлаус, [перевод с английского Д. Б. Подшивалова] — 2-е изд., испр. — СПб.: Нев. Диалект, 2001. — 351с.
Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд. – СПб.: БХВ-Петербург, 2011. – 720 с.
Седжвик Р. Фундаментальные алгоритмы на С++. Части 1 — 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах: Пер. с англ. – К.: Издательство “ДиаСофт”, 2001.
Окулов С.М. Программирование в алгоритмах. – 3-е изд. – М.: БИНОМ. Лаборатория знаний, 2007. – 383 с.
Шень А. Программирование: теоремы и задачи. М., МЦНМО, 2-е издание, 1995. – 263 с.
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Algorithms. — McGraw-Hill Companies, Incorporated, 2006. – 336 с.
Касьянов, В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев — СПб.: БХВ-Петербург, 2003- 1104 с.
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов.3-е изд. – СПб. : Питер, 2008. – 384 с.
Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Бином. Лаб. знаний, 2006. – 319 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979. – 536 с.
Бежанова М. М. Практическое программирование. Структуры данных и алгоритмы. — М.: Логос, 2001. — 223с.