Организация и функционирование компьютеров

l:=i+1 {Сдвигаем текущий элемент массива c}

end

else if (kn) or (a[j]>b[k])) then

{Массив b не кончился, а массив a кончился, либо массив a не кончился и

текущий элемент массива a больше текущего элемента массива b}

begin c[i]:=b[k]; {Записываем в массив c элемент массива b}

k:=k+1; {Сдвигаем текущий элемент массива b}

l:=i+1 {Сдвигаем текущий элемент массива a}

end

end;

Идея полного алгоритма сортировки массива слиянием заключается в следующем. Предположим для простоты, что длина массива равна степени двойки. Разобьем весь массив на пары соседних элементов и упорядочим каждку пару по возрастанию. Затем каждые две соседних пары сольем в одну упорядоченную четверку. В следующем цикле сольем каждые две соседних четверки в одну упорядоченную восьмерку и т.д. Для такого алгоритма необходима модификация описанной выше процедуры слияния, которая сливала бы два следующих друг за другом фрагмента одного массива и записывала результат в другой массив. Если длина массива не равна степени двойки, то сливаемые фрагменты массива могут иметь разную длину, но принципиально ничего не изменится.

Преимущество сортировки слиянием заключается в том, что один цикл слияния происходит за один проход всего массива и поэтому таким методом можно сливать не только массивы, но и большие файлы, списывая их фрагментами в массивы в оперативную память. Алгоритм при этом несколько усложняется, но принципиально остается тем же. Количество циклов при сортировке слиянием (число проходов по всему массиву или файлу) равно приблизительно log2n, где n – длина массива или файла.

Принципиально иной алгоритм сортировки основан на идее упорядочения массива по частям. Пусть m и M – минимальное и максимальное значения элементов массива. Положим b=(m+M)/2. Переставим элементы массива так, чтобы в начале шли ( в произвольном порядке) элементы, меньшие или равные b, а затем элементы большие b. Для этого будем двигаться одновременно с начала массива до элемента, большего b, и с конца массива до элемента, меньшего b. Как только мы их найдем, переставим эти элементы местами и начнем двигаться дальше. Процесс заканчивается тогда, когда мы встретимся где-то в середине массива. Соответствующий фрагмент программы на Паскале записывается так:

j:=1; k:=n; {Текущими являются первый и последний элементы массива}

while j

begin

while (jb}

while (jb) do k:=k-1; {Дойти до номера k, для которого a[k]

if j

a[j] :=a[k];

a[k]:=x

end

end;

После описанной процедуры осталось отсортировать отдельно первую часть массива (до конечного значения переменных j и k) и вторую часть массива. Для этого аналогичную процедуру нужно повторить для первой части массива и значения b1=(b+m)/2 и второй части массива и значения b2=(b+M)/2. Для полученных двух кусков первой и второй частей повторить то же самое и т.д. Процесс прекращается тогда, когда при делении образуются фрагменты массива длины 1. Конечно, процедуру нужно модифицировать таким образом, чтобы она умела разделять произвольные фрагменты массива с произвольным пороговым значением b.

Последний алгоритм, который мы здесь рассмотрим – это сортировка деревом. Предположим, что элементы массива размещены в вершинах бинарного дерева, то есть вершинами дерева будут номера элементов от 1 до n). Будем считать, что элемент a[k] подчиняет элементы a[2k] и a[2k+1] (если 2k+1 или 2k больше n, соответствующие стрелки в дереве отсутствуют). корнем дерева является элемент a[1]. Постараемся перестановками элементов добиться того, чтобы каждый отец был не меньше своих сыновей. Назовем такое дерево регулярным. Очевидно, максимальным в регулярном дереве является корень a[1]. Поменяем теперь элементы a[1] и a[n] и будем рассматривать оставшуюся часть массива длины n-1. Эта часть не будет регулярным деревом, так как оно испорчено: одна из вершин (с номером n) выкинута, а ее значение перенесено в корень. Однако испорчено оно несильно и его можно быстро исправить: корень дерева нужно поменять местами с максимальным из его сыновей, этого сына – с максимальным из его сыновей и т.д., пока очередная вершина не окажется больше своих сыновей либо их не будет вовсе. После этого в корне снова окажется максимальный элемент из оставшихся (n-1)-го, и его следует поменять с элементом a[n-1]. Производя подобную процедуру со все меньшими фрагментами массива, мы добьемся того, что массив будет весь отсортирован.