2015-01-30
528
Слияние q – серии из списка a с r – серией из списка b,
запись результата в очередь c
Слияние (a, q, b, r, c)
DO (q ≠ 0 и r ≠ 0)
IF (a → Data ≤ b → Data)
<Переместить элемент из списка a в очередь c>
q:=q-1
ELSE
<Переместить элемент из списка b в очередь c>
r:=r-1
FI
OD
DO (q > 0)
<переместить элемент из списка a в очередь c>
q:=q-1
OD
DO (r > 0)
<Переместить элемент из списка b в очередь c>
r:=r-1
OD
Для алгоритма слияния серий с длинами q и r необходимое количество сравнений и перемещений оценивается следующим образом
min (q, r) ≤ C ≤ q+r-1, M= q+r
Пусть длина списка S равна степени двойки, т.е. 2k, для некоторого натурального k. Разобьем последовательность S на два списка a и b, записывая поочередно элементы S в списки а и b. Сливаем списки a и b с образованием двойных серий, то есть одиночные элементы сливаются в упорядоченные пары, которые записываются попеременно в очереди c0 и c1. Переписываем очередь c0 в список a, очередь c1 – в список b. Вновь сливаем a и b с образованием серий длины 4 и т. д. На каждом итерации размер серий увеличивается вдвое. Сортировка заканчивается, когда длина серии превысит общее количество элементов в обоих списках. Если длина списка S не является степенью двойки, то некоторые серии в процессе сортировки могут быть короче.
|
|
|
Пример. Отсортировать слово методом прямого слияния.
| S | К | У | Р | А′ | П | О | В | А″ | Е′ | Л | Е″ | Н | А″′ | |
 a
| К | Р | П | В | Е′ | Е″ | А″′ | |||||||
| b | У | А′ | О | А″ | Л | Н | ||||||||
| a ← c0 | К | У | О | П | Е′ | Л | А″′ | |||||||
| b ←c1 | А′ | Р | А″ | В | Е′′ | Н | ||||||||
 a ← c0
| А′ | К | Р | У | Е′ | Е″ | Л | Н | ||||||
| b ←c1 | А″ | В | О | П | А″′ | |||||||||
 a ← c0
| А′ | А″ | В | К | О | П | Р | У | ||||||
| b ←c1 | А″′ | Е′ | Е″ | Л | Н | |||||||||
| Sc0 | А′ | А″ | А″′ | В | Е′ | Е″ | К | Л | Н | О | П | Р | У |
Рисунок 21 Метод прямого слияния
Схематически начальное расщепление последовательности S на списки a и b можно изобразить следующим образом. Ниже приведен алгоритм расщепление на псевдокоде при условии, что список S не пуст.
S
a
b
Рисунок 22 Начальное расщепление
|
|
|
Расщепление (S, a, b, n)
Обозначим
n - количество элементов в S
k, p - рабочие указатели
a:=S, b:=S → Next, n:=1
k:=a, p:=b
DO (p ≠ NIL)
n:=n+1
k → next:=p → next
k:=p
p:=p → next
OD
