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



         

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


Алгоритмы сортировки слиянием, как правило, имеют порядок 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; { нач.


    Содержание  Назад  Вперед