Алгоритмы порядка $n\,{\hbox{\rm log}}\,n$


$\scriptstyle{\blacktriangleright}$ 4.2.1. Предложить алгоритм сортировки, число действий которого было бы порядка $n\,\log n$, то есть не превосходило бы $Cn\log
n$ для некоторого C и для всех n .

  Мы предложим два решения.

Решение 1 (сортировка слиянием):

 

Пусть k -- положительное целое число. Разобьем массив ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ на отрезки длины k. (Первый -- ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[k]}}$, затем ${\hbox{\tt x[k+1]}}\ldots{\hbox{\tt x[2k]}}$ и так далее.) Последний отрезок будет неполным, если n не делится на k. Назовем массив k-упорядоченным, если каждый из этих отрезков в отдельности упорядочен. Любой массив 1-упорядочен. Если массив k-упорядочен и ${\hbox{\tt n}}\leqslant{\hbox{\tt k}}$, то он упорядочен.

Мы опишем, как преобразовать k-упорядоченный массив в 2k-упорядоченный (из тех же элементов). С помощью этого преобразования алгоритм записывается так:

 k:=1;
 {массив x является k-упорядоченным}
 while k < n do begin
 | ..преобразовать k-упорядоченный массив в 2k-упорядоченный;
 | k := 2 * k;
 end;

Требуемое преобразование состоит в том,что мы многократно << сливаем>> два упорядоченных отрезка длины не больше k в один упорядоченный отрезок. Пусть процедура \begin{displaymath}
{\hbox{\tt слияние (p,q,r: integer)}}\end{displaymath}при ${\hbox{\tt p}}\leqslant{\hbox{\tt q}}\leqslant{\hbox{\tt r}}$ сливает отрезки ${\hbox{\tt x[p+1]}}\ldots{\hbox{\tt x[q]}}$ и ${\hbox{\tt x[q+1]}}\ldots{\hbox{\tt x[r]}}$ в упорядоченный отрезок ${\hbox{\tt x[p+1]}}\ldots{\hbox{\tt x[r]}}$ (не затрагивая других частей массива x).

\begin{displaymath}
\begin{picture}
(20,6)

\thinlines 
 
\put(1,1){\line(1,0){1...
 ...tt q}}}}
\put(17,5){\makebox(1,1){{\hbox{\tt r}}}}\end{picture}\end{displaymath}Тогда преобразование k-упорядоченного массива в 2k-упорядоченный осуществляется так:

  t:=0;
  {t кратно 2k или t = n, x[1]..x[t] является
   2k-упорядоченным; остаток массива x не изменился}
  while t + k < n do begin
  | p := t;
  | q := t+k;
  | ...r := min (t+2*k, n); {min(a,b) - минимум из a и b}
  | слияние (p,q,r);
  | t := r;
  end;
Слияние требует вспомогательного массива для записи результатов слияния -- обозначим его b. Через p0 и q0 обозначим номера последних элементов участков, подвергшихся слиянию, s0 -- последний записанный в массив b элемент. На каждом шаге слияния производится одно из двух действий:

        b[s0+1]:=x[p0+1];
        p0:=p0+1;
        s0:=s0+1;
или
        b[s0+1]:=x[q0+1];
        q0:=q0+1;
        s0:=s0+1;
Первое действие (взятие элемента из первого отрезка) может производиться при одновременном выполнении двух условий: (1) первый отрезок не кончился (${\hbox{\tt p0}}<{\hbox{\tt q}}$);

(2) второй отрезок кончился (${\hbox{\tt q0}}={\hbox{\tt r}}$) или не кончился, но элемент в нем не меньше очередного элемента первого отрезка  [$({\hbox{\tt q0}} < {\hbox{\tt r}}$) и (${\hbox{\tt x[p0+1]}}\leqslant{\hbox{\tt x[q0+1]}}$)].

Аналогично для второго действия. Итак, получаем

  p0 := p; q0 := q; s0 := p;
  while (p0 <> q) or (q0 <> r) do begin
  | if (p0 < q) and ((q0 = r) or ((q0 < r) and
  | |                (x[p0+1] <= x[q0+1]))) then begin
  | | b [s0+1] := x [p0+1];
  | | p0 := p0+1;
  | | s0 := s0+1;
  | end else begin
  | | {(q0 < r) and ((p0 = q) or ((p0<q) and
  | |   (x[p0+1] >= x[q0+1])))}
  | | b [s0+1] := x [q0+1];
  | | q0 := q0 + 1;
  | | s0 := s0 + 1;
  | end;
  end;
(Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)

Остается лишь переписать результат слияния обратно в массив x.

Программа имеет привычный дефект: обращение к несуществующим элементам массива при вычислении булевских выражений. 


Решение 2 (сортировка деревом):

Нарисуем << полное двоичное дерево>> -- картинку, в    которой снизу один кружок, из него выходят стрелки в два других, из каждого -- в два других и так далее:

\begin{displaymath}
\begin{picture}
(6,5)
\put(3,1){\circle*{.15}}
\put(2,2){\ci...
 ...){.33333333}}
\put(4.5,3){\vector(1,3){.33333333}}\end{picture}\end{displaymath}

Будем говорить, что стрелки ведут << от отцов к сыновьям>>: у каждого кружка два сына и один отец (если кружок не в самом верху или низу). Предположим для простоты, что количество подлежащих сортировке чисел есть степень двойки, и они могут заполнить один из рядов целиком. Запишем их туда. Затем заполним часть дерева под ними по правилу: \begin{displaymath}
{\hbox{\rm число в кружке = минимум из чисел в кружках-сыновьях}}\end{displaymath}Тем самым в корне дерева (нижнем кружке) будет записано минимальное число во всем массиве.

Изымем из сортируемого массива минимальный элемент. Для этого его надо вначале найти. Это можно сделать, идя от корня: от отца переходим к тому сыну, где записано то же число. Изъяв минимальный элемент, заменим его символом $+\infty$ и скорректируем более низкие ярусы (для этого надо снова пройти путь к корню). При этом считаем, что $\min(t,+\infty)=t$.Тогда в корне появится второй по величине элемент, мы изымаем его, заменяя бесконечностью и корректируя дерево. Так постепенно мы изымем все элементы в порядке возрастания, пока в корне не останется бесконечность.

При записи этого алгоритма полезно нумеровать кружки числами ${\hbox{\tt 1}},{\hbox{\tt 2}},\ldots$ -- при этом сыновьями кружка номер n являются кружки 2n и ${\hbox{\tt 2n}}+{\hbox{\tt 1}}$. Подробное изложение этого алгоритма мы опустим, поскольку мы изложим более эффективный вариант, не требующий дополнительной памяти, кроме конечного числа переменных (в дополнение к сортируемому массиву).

Мы будем записывать сортируемые числа во всех вершинах дерева, а не только на верхнем уровне. Пусть ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ -- массив, подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о числе x[i] мы будем говорить как о числе, стоящем в вершине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в переменной k. Таким образом, в процессе работы алгоритма массив ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$делится на две части: в ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[k]}}$ хранятся числа на дереве, а в ${\hbox{\tt x[k+1]}}\ldots{\hbox{\tt x[n]}}$ хранится уже отсортированная в порядке возрастания часть массива -- элементы, уже занявшие свое законное место.

На каждом шаге алгоритм будет изымать максимальный элемент дерева и помещать его в отсортированную часть, на освободившееся в результате сокращения дерева место.

Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть сыновья 2s и 2s+1. Если оба этих числа больше k, то сыновей нет; такая вершина называется листом. Если ${\hbox{\tt 2s}}={\hbox{\tt k}}$, то вершина s имеет ровно одного сына (2s).

Для каждого s из ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$ рассмотрим << поддерево>> с корнем в s: оно содержит вершину s и всех ее потомков (сыновей, внуков и так далее -- до тех пор, пока мы не выйдем из отрезка ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$). Вершину s будем называть регулярной, если стоящее в ней число -- максимальный элемент s-поддерева; s-поддерево назовем регулярным, если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.)

Схема алгоритма такова:

 k:= n
 ... Сделать 1-поддерево регулярным;
 {x[1],..,x[k] <= x[k+1] <=..<= x[n]; 1-поддерево регулярно,
  в частности, x[1] - максимальный элемент среди x[1]..x[k]}
 while k <> 1 do begin
 | ... обменять местами x[1] и x[k];
 | k := k - 1;
 | {x[1]..x[k-1] <= x[k] <=...<= x[n]; 1-поддерево регу-
 |   лярно везде, кроме, возможно, самого корня }
 | ... восстановить регулярность 1-поддерева всюду
 end;
В качестве вспомогательной процедуры нам понадобится процедура восстановления регулярности s-поддерева в корне. Вот она:
  {s-поддерево регулярно везде, кроме, возможно, корня}
  t := s;
  {s-поддерево регулярно везде, кроме, возможно, вершины t}
  while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
  |     ((2*t <= k) and (x[2*t] > x[t])) do begin
  | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
  | | ... обменять x[t] и x[2*t+1];
  | | t := 2*t + 1;
  | end else begin
  | | ... обменять x[t] и x[2*t];
  | | t := 2*t;
  | end;
  end;

Чтобы убедиться в правильности этой процедуры, посмотрим на нее повнимательнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим сыновей вершины t. Они регулярны, и потому содержат наибольшие числа в своих поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве могут претендовать число в самой вершине t и числа в ее сыновьях. (В первом случае вершина t регулярна, и все в порядке.) В этих терминах цикл можно записать так:

while наибольшее число не в t, а в одном из сыновей do begin
| if оно в правом сыне then begin
| | поменять t с ее правым сыном; t:= правый сын
| end else begin {наибольшее число - в левом сыне}
| | поменять t с ее левым сыном; t:= левый сын
| end
end
После обмена вершина t становится регулярной (в нее попадает максимальное число t-поддерева). Не принявший участия в обмене сын остается регулярным, а принявший участие может и не быть регулярным. В остальных вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева переставились), так что регулярность не нарушилась. Эта же процедура может использоваться для того, чтобы сделать 1-поддерево регулярным на начальной стадии сортировки:
  k := n;
  u := n;
  {все s-поддеревья с s>u регулярны }
  while u<>0 do begin
  | {u-поддерево регулярно везде, кроме разве что корня}
  | ... восстановить регулярность u-поддерева в корне;
  | u:=u-1;
  end;

Теперь запишем процедуру сортировки на паскале (предполагая, что n -- константа, x имеет тип arr = array [1..n] of integer).

  procedure sort (var x: arr);
  | var u, k: integer;
  | procedure exchange(i, j: integer);
  | | var tmp: integer;
  | | begin
  | | tmp  := x[i];
  | | x[i] := x[j];
  | | x[j] := tmp;
  | end;
  | procedure restore (s: integer);
  | | var t: integer;
  | | begin
  | | t:=s;
  | | while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
  | | |     ((2*t <= k) and (x[2*t] > x[t])) do begin
  | | | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
  | | | | exchange (t, 2*t+1);
  | | | | t := 2*t+1;
  | | | end else begin
  | | | | exchange (t, 2*t);
  | | | | t := 2*t;
  | | | end;
  | | end;
  | end;
  begin
  | k:=n;
  | u:=n;
  | while u <> 0 do begin
  | | restore (u);
  | | u := u - 1;
  | end;
  | while k <> 1 do begin
  | | exchange (1, k);
  | | k := k - 1;
  | | restore (1);
  | end;
  end;`


Несколько замечаний

Метод, использованный при сортировке деревом, бывает полезным в других случах. (См. в главе 6 (о типах данных) об очереди с приоритетами.)

Сортировка слиянием хороша тем, что она на требует, чтобы  весь сортируемый массив помещался в оперативной памяти. Можно сначала отсортировать такие куски, которые помещаются в памяти (например, с помощью дерева), а затем сливать полученные файлы.

Еще один практически важный алгоритм сортировки (быстрая сортировка Хоара) таков:   чтобы отсортировать массив, выберем случайный его элемент b , и разобьем массив на три части: меньшие b , равные b и большие b . (Эта задача приведена в главе 1.) Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма -- случайная величина; можно доказать, что в среднем он работает не больше $Cn\log
n$.На практике -- он один из самых быстрых. (Мы еще вернемся к нему, приведя его рекурсивную и нерекурсивную реализации.)

Наконец, отметим, что сортировка за время порядка $Cn\log
n$может быть выполнена с помощью техники сбалансированных деревьев (см. главу 12), однако программы тут сложнее и константа C довольно велика.



pvv
1/8/1999