Сортировка слиянием
Сортировка слиянием (метод простого двухпутевого слияния)
В основе данного метода
внутренней сортировки лежит процедура слияния
двух упорядоченных таблиц. Эти
таблицы должны быть объединены таким образом,
чтобы получилась одна упорядоченная таблица.
Пусть имеются две таблицы А и В, упорядоченные по
возрастанию ключей . Слияние заключается в
поочередной пересылке элементов из таблиц А и В в
зону формирования С. Порядок пересылки в зону
формирования зависит от результата попарного
сравнения ключей таблиц А и В.
Сортировка слиянием производится на
основе использования рассмотренной выше
процедуры. Сущность сортировки состоит
в том, что упорядочиваемая таблица разделяется
на равные группы элементов. Группы
упорядочиваются, а затем попарно сливаются,
образуя новые группы, содержащие вдвое больше
элементов.
Процедура слияния двух групп должна иметь такие
параметры:
TAB - имя сортируемой таблицы;
n - длина таблицы (количество записей);
i1,i2 - начальные индексы сливаемых групп;
l1,l2 - длины сливаемых групп;
h - шаг слияния;
PS - поле слияния.
TAB TAB
--------------- ---------------
¦ .
. .
¦ ¦ . .
. ¦
i1 +-------------+
------- i1 +-------------+
¦ 23 ¦ l1
¦ 17
¦ ¦
17 ¦
¦
68 ¦
+-----+ ¦
19 ¦
i2
+-------------+ ¦ 19
¦ ¦
23 ¦
¦
17 ¦
+-----+ ¦
68 ¦
¦
19 ¦ l2 ¦
23 ¦
¦ ¦
+-------------+
+-----+ +-------------+
¦ ¦
¦ 68 ¦
¦ ¦
¦
. .
. ¦
------ ¦ . .
. ¦
-------------- --------------
На первом этапе каждая группа содержит
два соседних элемента исходного
массива. Элементы внутри групп упорядочиваются
(напр., методом вставки). Затем происходит
попарное слияние групп. Количество групп в
списке уменьшается вдвое до тех пор, пока не
будет получена одна упорядоченная группа. Если
число элементов нечетное, то вводится
дополнительный элемент с максимальным значением.
После сортировки он отбрасывается. Если число
групп, сформированных на первом этапе, нечетно,
то непарная группа переписывается без
слияния. Рассмотренный метод
двухпутевой сортировки слиянием весьма
эффективен. Поскольку при сортировке
нужно выполнить log2(n) проходов,то необходимое
суммарное число сравнений равно,примерно,n*log2(n).
Одним из недостатков данного метода
является требование большого резерва памяти:
S =
[n/2].
Сортировка слиянием (естественное слияние)
Метод простого слияния никак
не учитывает тот факт,что в таблице
могут быть сразу или получаться на некотором
шаге упорядоченые группы записей длиной m и l,которые
можно сразу объединить в одну упорядоченную
группу длиной m+l (более того,эти упорядоченные
последовательности могут разрываться,их
элементы будут относиться к разным группам).
Сортировка,при которой сливаются рядом стоящие
упорядоченные группы произвольной длины,называется
естественным слиянием. Цель естественного
слияния-исключить лишние просмотры. Процедура
слияния двух групп такая же,как и в методе
простого слияния,но длины l1 и l2 сливаемых групп
нужно каждый раз подсчитывать,сравнивая ключи
двух рядом стоящих записей (можно составить
массив длин упорядоченных групп).
Содержание
|
