Модели и структуры данных
       

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


Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внеш- ней сортировки, которая более подробно будет рассматриваться нами во втором томе нашего пособия. Здесь же для понимания принципа слияния мы приводим простейший алгоритм слияния в оперативной памяти.

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

Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одно-элементных множества сливаются в одно двух-элементное упорядоченное множество. На втором проходе двух-элементные множества сливаются в 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. Для каждого прохода показаны множества, которые на этом проходе сливаются. Обратите внимание на обработку последнего множества, оставшегося без пары.



    Таблица 3.11

    КаталогИндекс раздела
    НазадОглавлениеВперед

    Содержание раздела