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

Обновлено: 07.07.2024

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

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

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

Таким образом, задачами курсовой работы являются:

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

- определить основные параметры оценки алгоритмов сортировки;

- рассмотреть различные методы сортировки данных;

- разработать алгоритм решения экономической задачи, представленной в практической части работы;

- использовать в работе, в целях более наглядного восприятия, шаблоны

выходных документов, показав их расположение на рабочем листе

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

I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Что представляет собой алгоритм сортировки

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

Алгоритм сортировки — это порядок действий для упорядочения элементов в списке. Обычно говорят о сортировке записей (содержащих любые данные) по ключам – фрагментам этих записей, допускающих отношение упорядочения. Например, ключи могут быть числами (в этом случае используется естественный математический порядок возрастания или убывания чисел) или строковыми значениями (в этом случае упорядочение производится по алфавиту). [4, стр. 195]

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

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

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

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

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

• Естественность поведения — эффективность метода при обработке уже

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

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

Алгоритмы сортировки данных

Существует множество методов сортировки, каждый из которых имеет свои достоинства и недостатки.

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

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

Обменная сортировка

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

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

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

1. Сначала верхняя граница устанавливается равной размеру массива.

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

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

4. Если обменов не было вообще, алгоритм заканчивает работу.

Сортировка перемешиванием

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

Сортировка вставками

Другие методы сортировки производят реальное переупорядочивание набора записей. Сортировка вставками основывается на описанной далее идее.

1. Начнем формировать новый отсортированный массив.

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

3. Когда все записи перенесены в новый массив, данные располагаются в отсортированном порядке.

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

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

Блочная сортировка

Наиболее известным методом блочной сортировки является метод Шелла.

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

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

Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Время работы сортировки слиянием намного меньше, чем у пузырьковой сортировки. [6]

Пирамидальная сортировка

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

После первого этапа работы алгоритма массив данных преобразуется таким образом, что максимальный элемент (временно) размещается в самой первой записи и для всех элементов верны неравенства: a (j) > a (2*j) и a(j) > a (2*j+1), если соответствующие элементы все еще лежат внутри массива. Пари этом a – элемент массива; j – его порядковый номер. Последующие этапы работы алгоритма приводят к тому, что максимальный в данный момент элемент отправляется на правильное место в отсортированном массиве, а для всех остальных элементов сохраняются такие же неравенства. [5, стр. 214-215]

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

· Каждый лист имеет определенную глубину;

· Значение в любой вершине больше, чем значения ее потомков.

И первоначальное преобразование, и последующий этап работы требует относительно небольшого числа операций, так что на больших массивах получается значительный выигрыш. Особенность этого алгоритма состоит в том, что он хорошо работает при любом начальном порядке данных в массиве, в то время как некоторые более быстрые (в среднем) методы могут очень неудачно обрабатывать определенные, специально подобранные наборы данных. [8]

Линейная сортировка (сортировка отбором)

Идея линейной сортировки по невозрастанию заключается в том, что

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

по дисциплине Практикум по программированию С++

Студенту Капралову Сергею Алексеевичу группы СИБ 20-3

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

Задание выдано " 21 " января 2021 г.

Руководитель подпись

Студент подпись

Содержания
Введение……………………………………………………………….……….4
1. Теоретическая часть
1.1 Основные понятия……………..………………………………………..5
1.2. Классификация элементов алгоритма сортировки……………….6
1.3. Характеристика методов сортировки…………………………8
Практическая часть (вариант № 5)
2. Задание…………………………………………………………………11
3. Тестирование программы…………………………………………. 11
Таблица времени сортировки …………………………………………..13
Заключение………………………………………………………………. 13
Список литературы ……………………………………………………14
Приложение А листинг программы…………………………………….15
Приложение Б Антиплагиат …………………………………………….20

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

1. Теоретическая часть.

1.1. Основные понятия

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

Сортировка пузырьком.
Сортировка перемешиванием.
Сортировка методом вставок.
Сортировка подсчетом.
Сортировка слиянием.
Цифровая сортировка.
Сортировка методом выбора.
Сортировка методом Шелла.
Обменная поразрядная сортировка.
Пирамидальная сортировка.
Сортировка массивом (хеширование).
Быстрая сортировка (метод Хоара).
Блочная сортировка.

В любом алгоритме сортировки есть сравнение и перестановка, отличаются сортировки затратой памяти, временем и алгоритмами.

1.2. Классификация элементов алгоритма сортировки
Написание любого алгоритма имеет несколько важных свойств:

4. дискретность
Определённость алгоритма значит, что алгоритм должен быть понятен любому пользователю, и он смог его повторить.
Массовость отвечает за предназначение алгоритма для решения класса задач.

Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.
Дискретность алгоритма означает, что алгоритм исполняется по шагам, то есть каждое новое действие алгоритма должно исполняться только после того, как предыдущее действие закончило свою задачу.
Как можно представить алгоритм:
1. Алгоритм можно представить словесно,

2. В виде схемы будь то просто картинка или гиф изображение, что даже лучше,

3. Можно показать программой на языке программирования,

4. В словесно-аналитической форме.
Какие виды алгоритмических структур бывают?

1. Линейный - все команды исполняются последовательно.

2. Разветвляющийся - действия происходят в зависимости от условия, работает либо одна серия команд, либо другая.

3. Циклический - повторяется некоторый участок алгоритма
Сфера применения
Внутренняя сортировка - работа с массивом данных, целиком расположенном в памяти и возможным доступом к его любому элементу.
Внешняя сортировка - характеризуется работой с данными большого объема и последовательным доступом к отдельным элементам списка. Применяется, например, при упорядочении файлов.
1.3. Характеристика алгоритмов сортировки:
Сортировка пузырьком.

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

Сортировка вставками.

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

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

Сортировка слиянием (от англ. merge sort) алгоритм сортировки для упорядочивания списков или других структур данных доступ к которым можно получать исключительно последовательно. Сортировка слиянием это отличный пример принципа “разделяй и властвуй”. Для начала задача разбивается на несколько подзадач. После эти задачи решаются рекурсивным вызовом (Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.) или непосредственно, если имеют небольшой размер. После всех действий их решения комбинируются, и получается исходное решение.

Сортировка выбором.

Сортировка выбором (от англ. Selection sort) алгоритм сортировки, который может быть как устойчивым, так и неустойчивым.

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

2. меняем значения позиций минимального значения на значение первой, не отсортированной позиции (не меняем, если минимальный элемент уже находится на данной позиции)

3. сортируем хвост нашего списка, исключая уже отсортированные элементы

Сортировка шелла.

Сортировка шелла (от англ. Shell sort) – усовершенствованная версия алгоритма сортировки методом вставок. Метод шелла сравнивает элементы стоящие не только рядом, но и на расстоянии друг от друга. Работа сортировки шелла заключается в том, что сначала сравниваются и сортируются значения, стоящие на некотором расстоянии друг от друга. После те же действия повторяются для некоторых меньших значений, а завешается сортировка Шелла упорядочиванием элементов (то есть обычной сортировкой вставками).

Практическая часть
2. Задание Сортировка массива методом слияния

Цель работы: Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно заполняется случайными числами. Добавить возможность предварительной сортировки начальных серий методом простой вставки. Провести статистические наблюдения над временем работы сортировки слиянием: без предварительной сортировки начальных серий; с отсортированными начальными сериями, размером 8, 16 элементов. Время подготовки начальных серий также учитывается при замере. Выбор варианта статистического наблюдения вводится с клавиатуры.
В процессе работы были созданы две функции для работы сортировки методом “вставок” и сортировки методом “слияния”.
3. Тестирование программы и сортировки методом слияния в разных случаях на время работы

Для работы было разработано 2 функции сортировки вставок (по 8 элементов и по 16 элементов) разработана функция сортировки слияния. В данной программе использовалась функция для подсчёта тиков (для более точного подсчёта сортировка была внесена в цикл на 100000 повторений) QueryPerformanceCounter находящаяся в библиотеке “Windows.h”. Размер массива вводится в консоли, заполнение массива идёт с помощью rand(), а дальше пользователь выбирает метод сортировки.

Отчёт на работоспособность программы
Для начала вводим размер массива (количество элементов в списке)

Ввели размер массива на 32 элемента, дальше нас просят выбрать метод.

Так как все сортировки были внесены под цикл на 100000 повторений, делим 573,399/100000 = 0,00573399

571,408 / 100000 = 0,00571408

Таблица времени сортировки

Количество элементов массива	Сортировка слиянием с пред.сорт. по 8 элементов	Сортировка слиянием с пред.сорт. по 16 элементов	Сортировка слиянием
16	0,0066417	0,0069602	0,0072047
32	0,00128713	0,00127972	0,00129745
48	0,00215212	0,00216897	0,00213767
64	0,00282832	0,00279639	0,00281918
80	0,00424183	0,00368384	0,00371180
96	0,00439119	0,00441727	0,00437333
112	0,00516112	0,00513841	0,00517013
128	0,00573399	0,00571408	0,00572517
144	0,00735195	0,00727936	0,00729271
160	0,00795910	0,00803087	0,00802668

Смотря на таблицу можно сделать вывод, что сортировка слиянием с предварительной сортировкой вставками по16 и по 8 элементов делают сортировку быстрее, но не всегда. В программе, где массив на 48, 96, элементов видно, что сортировка слиянием справилась быстрее с обычным не отсортированным предварительно массивом, нежели с отсортированными массивами.
Заключение

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

__int64 CounterStart = 0;
void StartCounter()

int* arr = new int[size]; // создаем массив
//для сортировки вставками по несколько элементов-->>

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

Содержание

ВВЕДЕНИЕ…………………………………………………………………………5
1 ПОСТАНОВКА ЗАДАЧИ……………………………………………………. 7
2 АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ………………………………8
2.1 ОБЩАЯ СХЕМА
ФУНКЦИОНИРОВАНИЯ………………………………………………8
2.2 ОЦЕНКА АЛГОРИТМА
СОРТИРОВКИ…………………………………………………………. 11
3 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ……………………………………..12
4 КОНТРОЛЬНЫЙ ПРИМЕР……………………………………………………. 13
5 ЗАКЛЮЧЕНИЕ…………………………………………………………………. 14
6 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ…………………………… 15

Вложенные файлы: 1 файл

Algoritmy_i_struktury_dannykh_Kursovaya.docx

Отчет 16с., 2р., 5 источников, 1 прил.

ЕСТЕСТВЕНОЕ СЛИЯНИЕ; ВНЕШНЯЯ СОРТИРОВКА

Объектом исследования являются алгоритм сортировки естественным слиянием.

Цель работы – реализация сортировки естественного слияния.

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

В результате проделанной работы была реализована сортировка естественного слияния.

2 АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ………………………………8

2.2 ОЦЕНКА АЛГОРИТМА

3 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ……………………………………. .12

4 КОНТРОЛЬНЫЙ ПРИМЕР……………………………… ……………………. 13

6 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ…………………………… 15

ПРИЛОЖЕНИЕ А. ТЕКСТЫ ОСНОВНЫХ ПРОГРАММНЫХ МОДУЛЕЙ….16

Алгоритмы внешней сортировки:

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

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

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

В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения.

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

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

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

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

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ

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

2. АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ

2.1 ОБЩАЯ СХЕМА ФУНКЦИОНИРОВАНИЯ

Данная сортировка является улучшением сортировки слиянием и относится к внешним сортировкам.

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

Сортировка слиянием относится к устойчивым методам сортировки.

Общий алгоритм сортировки слиянием

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

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

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

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

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

Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.

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

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2. Распределение происходит следующим образом: поочередно считываются записи a_i исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(a_i) f(a_i+1), то записи a_i+1 копируются во второй вспомогательный файл f2. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.

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

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

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

Символ "`" обозначает признак конца серии.

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

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

Рис. 1 Иллюстрация действия алгоритма сотрировки естественным слиянием

2.2 ОЦЕНКА АЛГОРИТМА СОРТИРОВКИ

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

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

Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Алгоритм сортировки естественным слиянием требует для своей работы создания двух вспомогательных файлов, содержащих в среднем по n\2 элементов исходного набора, в худшем случае один из файлов содержит n-1 элементов, а второй всего один. Дополнительных переменных для хранения промежуточных результатов не требуется.

ТАБЛИЦА ПРОЦЕДУР И ФУНКЦИЙ

В данной таблице будет представлено две процедуры. Процедура сортировки Шелла и процедура сортировки вставками.

ГОСТ

Алгоритм сортировки слиянием — это алгоритм, выполняющий упорядочивание списков в требуемом порядке.

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

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

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

Процесс однократной обработки некоторого количества данных является фазой. Самый маленький подпроцесс, который путём многократных повторений формирует всю процедуру, именуется этапом. Операция слияния подразумевает соединение пары, изначально прошедших упорядочивание подпоследовательностей, имеющих размерность N/2, в одну последовательность с размерностью n. Первые компоненты последовательностей, прошедших предварительное упорядочивание, проходят процедуру сравнения друг с другом, и в итоге определяется самый маленький. Затем нужный указатель переставляется на последующий компонент. Далее осуществляется повтор операции до момента достижения конца какой-либо подпоследовательности. Остальные компоненты другой подпоследовательности пересылаются в итоговую последовательность без всяких изменений. Пример приведён ниже:

Рисунок 1. Последовательность. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

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

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

Двухпутевое слияние

Алгоритм двухпутевого слияния заключается в следующем. Начальная последовательность делится на пару последовательностей:

Рисунок 2. Последовательность. Автор24 — интернет-биржа студенческих работ

Рисунок 3. Последовательность. Автор24 — интернет-биржа студенческих работ

Полученные последовательности затем проходят процесс объединения в единую последовательность, которая содержит упорядоченные пары:

Рисунок 4. Последовательность. Автор24 — интернет-биржа студенческих работ

Эту операцию следует выполнять до момента, пока сформированная последовательность не станет по размерам равна сортируемой.

Читайте также: