Сортировка попарным слиянием.
Сортировка попарным слиянием.
Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одно-элементных множества сливаются в одно двух-элементное упорядоченное множество. На втором проходе двух-элементные множества сливаются в 4-элементные упорядоченные множества и т.д. В конце концов мы получаем одно большое упорядоченное множество.
Важнейшей частью алгоритма является слияние двух упорядоченных множеств. Эту часть алгоритма мы опишем строго.
- 1. [Начальные установки]. Определить длины первого и второго исходных множеств - l1 и l2 соответственно. Установить индексы текущих элементов в исходных множествах i1 и i2 в 1. Установить индекс в выходном множестве j=1.
- 2. [Цикл слияния]. Выполнять шаг 3 до тех пор, пока i13. [Сравнение]. Сравнить ключ i1-го элемента из 1-го исходного множества с ключом i2-го элемента из второго исходного множества. Если ключ элемента из 1-го множества меньше, то записать i1-ый элемент из 1-го множества на j-ое место в выходное множество и увеличить i1 на 1. Иначе - записать i2-ой элемент из 2-го множества на j-ое место в выходное множество и увеличить i2 на 1. Увеличить j на 1.
- 4. [Вывод остатка]. Если i1
Программный пример 3.17 иллюстрирует сортировку попарным слиянием в ее обменном варианте - выходные множества формируются на месте входных.
{===== Программный пример 3.17 =====} { Сортировка слиянием } Procedure Sort(var a :Seq); Var i0,j0,i,j,si,sj,k,ke,t,m : integer; begin si:=1; { начальный размер одного множества } while si < N do begin { цикл пока одно множество не составит весь массив } i0:=1; { нач. индекс 1-го множества пары } while i0 < N do begin { цикл пока не пересмотрим весь массив } j0:=i0+si; { нач. индекс 2-го множества пары } i:=i0; j:=j0; { размер 2-го множества пары может ограничиваться концом массива } if si > N-j0+1 then sj:=N-j0+1 else sj:=si; if sj > 0 then begin k:=i0; { нач. индекс слитого множества } while (i < i0+si+sj) and (j a[j] then begin { если эл-т 1-го a[j] } k:=k+1; { вых. множество увеличилось } i:=i+1; { если был перенос - за счет сдвига, если не было - за счет перехода эл-та в вых. } end; { while } end; { if sj > 0 } i0:=i0+si*2; { начало следующей пары } end; { while i0 < N } si:=si*2; { размер эл-тов пары увеличивается вдвое } end; { while si < N } end;Результаты трассировки примера приведены в таблице 3.11. Для каждого прохода показаны множества, которые на этом проходе сливаются. Обратите внимание на обработку последнего множества, оставшегося без пары.