Естественное двухпутевое слияние реферат

Обновлено: 02.07.2024

Рис. 5 иллюстрирует сортировку слиянием, когда мы продвигаемся с обоих концов, подобно методам быстрой сортировки, обменной сортировки и т.д. Мы анализируем исходный файл слева и справа, двигаясь к середине. Пропустим первую строку и рассмотрим вторую. Слева мы видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который перемещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 987 и результат записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается раньше, чем оно может привести к нежелательным последствиям) и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1.

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

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

Алгоритм Е (Сортировка естественным двухпутевым слиянием).

При сортировке записей R₁, …, R_N используются две области памяти, каждая из которых может содержать N записей. Для удобства обозначим записи, находящиеся во второй области, через R_N+1, …, R_2N, хотя в действительности области не обязательно идти друг за другом. Начальное содержание второй области не имеет значение. После завершения алгоритма ключи будут упорядочены К₁ £ …£ К_N.

Блок-схема, построенная в соответствии с принципами структурного программирования

(Начальная установка) Установить s:=0 (при s=0 мы будем пересылать записи из области (R₁,…R_N) в область (R_N+1, …, R_2N); при s=1 наоборот.)

(Подготовиться к просмотру) Если s=0, то установить i:=1, j:=N, k:=N+1, g:=2N, если s=1, то установить i:=N+1, j:=2N, k:=1, g:=N. (переменные i, j, k, g указывают текущие позиции во входных "файлах", откуда идет чтение, и в "выходных" файлах, куда идет запись; i и k – левые позиции, j и r – правые позиции.) Установить d:=1, f:=1 (Переменные d определяет текущее направление вывода, f устанавливается равной 0, если необходимы дальнейшие просмотры.)

(Сравнения К_i с К_j) Если К_i > К_j, то перейти к шагу Е8, если i=j (т.е. рассматриваем один и тот же элемент с разных концов), то установить R_k:=R_i и перейти к шагу Е13.

(Пересылка R_i) (Шаги Е4-Е7 аналогичны шагам М3-М4 алгоритма М). Установить R_k:=R_i, k:=k+d.

(Ступенька вниз?) Увеличить i на 1, Затем, если К_i–1 £ К_i, то возвратиться к шагу Е3.

(Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1 £ К_j, то возвратиться к шагу Е6, в противном случае перейти к шагу Е12.

(Пересылка R_j) (Шаги Е8–Е11 двойственные по отношению к шагам Е4–Е7) Установить R_k:=R_j, k:=k+d.

(Ступенька вниз?). Уменьшить j на 1. Затем, если К_j+1 £ К_j, то возвратиться к шагу Е3

(Ступенька вниз?). Увеличить i на 1, Затем, если К_i–1 £ К_i, то возвратиться к шагу Е10.

(Переключение направления). Установить f:=0, d:= – d и взаимозаменить k g. Возвратиться к шагу Е3.

(Переключение областей) Если f=0, то установить s:=1–s и возвратиться к шагу Е2, в противном случае сортировка завершена, если s=0, то установить (R₁,…R_N) := (R_N+1, …, R_2N) (если это критично).

ГОСТ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ключевые термины

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

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

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

Длина серии – это количество элементов в серии.

Естественное слияние – это сортировка , при которой всегда сливаются две самые длинные из возможных серий.

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

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

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

Простое слияние – это одна из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге.

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

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

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

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

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

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