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

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

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

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

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

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

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

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

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

на тему:

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

Выполнил:

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

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

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

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

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

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

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

Якушин А.В.

Тула-2015

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

Приложения

Приложение 1

Приложение 2

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 Алгоритм сортировки естественным слиянием

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

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

№ прохода	Распределение	Слияние
1	М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
2	М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 Оценка сложности алгоритма

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

1) Время -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение -- это O(n log n) и плохое поведение -- это O(nІ). Идеальное поведение для упорядочения -- O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;

2) Память -- ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

3)Устойчивость (stability) -- устойчивая сортировка не меняет взаимного расположения равных элементов.

4)Естественность поведения -- эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Глава 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. Тестирование

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

· продемонстрировать разработчикам и заказчикам, что программа соответствует требованиям;

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

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

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

§ Функциональное тестирование

§ Тестирование производительности

§ Юзабилити-тестирование

§ Тестирование интерфейса пользователя

§ Тестирование безопасности

§ Тестирование локализации

§ Тестирование совместимости

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

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

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

§ Тестирование серого ящика

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

§ Ручное тестирование

§ Автоматизированное тестирование

§ Полуавтоматизированное тестирование

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

§ Компонентное (модульное) тестирование

§ Интеграционное тестирование

§ Системное тестирование

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

§ Альфа-тестирование

§ Бета-тестирование

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

§ Позитивное тестирование

§ Негативное тестирование

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

§ Тестирование по документации

§ Тестирование ad hoc или интуитивное тестирование

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

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

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

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

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

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

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

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

Заключение

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

Заданная цель и поставленные цели в полной мере были реализованы.

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

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

1. Ахо, Альфред, В., Хопкрофт, Джон, Уильман, Джеффри, Д., Структуры данных и алгоритмы.: Издательский дом «Вильямс», 2000.

2. Вирт, Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.

3. Кормен Т., Леверсон Ч., Ривест Р. Алгоритмы. Построение и анализ / Т. Кормен, Ч. Леверсон, Р. Ривест. - М.: МЦНМО, 1999.

4. Макконнелл Дж., Основы современных алгоритмов. 2-е дополнительное издание -- Москва, 2004.

5. Мальцев А. И., Алгоритмы и рекурсивные функции, -- 2-е издание, 1986.

6. Окулов С. М., Программирование в алгоритмах, М.: БИНОМ. Лаборатория знаний, 2002.

7. Подбельский, В.В. Программирование на языке Си: учеб.пособие / В.В. Подбельский, С.С. Фомин. - М.: Финансы и статистика, 2004.

8. Подбельский, В.В. Язык Си++: учеб.пособие / В.В. Подбельский. - М.: Финансы и статистика, 2005.

9. Седжвик Роберт, Фундаментальные алгоритмы на С++. Анализ/ структуры данных/ сортировка/ поиск, 2001.

10. Сундукова, Т.О., Ваныкина, Г.В.. Структуры и алгоритмы компьютерной обработки данных [Электронный ресурс]: INTUIT.RU: Учебный курс -- Структуры и алгоритмы компьютерной обработки данных / Интернет-Университет Информационных технологий. -- 2006. Режим доступа: http://www.intuit.ru/studies/courses/648/504/lecture/.

11. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие / Б.С. Хусаинов. - М.: Финансы и статистика, 2004.

Приложения

Приложение 1

Проверка на корректность ввода пункта меню

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

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

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

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

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

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

Приложение 2

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

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

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