упорядоченный отрезок x[p+1]..x[r] (не затрагивая других частей
массива x).
p q r
-------|---------------|---------------|-------
| упорядоченный | упорядоченный |
-------|---------------|---------------|-------
|
|
V
-------|-------------------------------|-------
| упорядоченный |
-------|-------------------------------|-------
Тогда преобразование 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 }
| слияние (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) первый отрезок не кончился (p0 < q);
(2) второй отрезок кончился (q0 = r) или не кончился, но
элемент в нем не меньше [(q0 < r) и (x[p0+1] <= 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= x[q0+1])))}
| | b [s0+1] := x [q0+1];
| | q0 := q0 + 1;
| | s0 := s0 + 1;
| end;
end;
(Если оба отрезка не кончены и первые невыбранные элементы в них
равны, то допустимы оба действия; в программе выбрано первое.)
Программа имеет привычный дефект: обращение к несуществу-
ющим элементам массива при вычислении булевских выражений.
Решение 2 (сортировка деревом).
Нарисуем "полное двоичное дерево" - картинку, в которой
снизу один кружок, из него выходят стрелки в два других, из каж-
дого - в два других и так далее:
.............
o o o o
\/ \/
o o
\ /
o
Будем говорить, что стрелки ведут "от отцов к сыновьям": у
каждого кружка два сына и один отец (если кружок не верхний).
Предположим для простоты, что количество подлежащих сортировке
чисел есть степень двойки, и они могут заполнить один из рядов
целиком. Запишем их туда. Затем заполним часть дерева под ним по
правилу:
число в кружке = минимум из чисел в кружках-сыновьях
Тем самым в корне дерева (нижнем кружке) будет записано мини-
мальное число во всем массиве.
Изымем из сортируемого массива минимальный элемент. Для
этого его надо вначале найти. Это можно сделать, идя от корня:
от отца переходим к тому сыну, где записано то же число. Изъяв
минимальный элемент, заменим его символом "бесконечность" и
скорректируем более низкие ярусы (для этого надо снова пройти
путь к корню). При этом считаем, что минимум из n и бесконечнос-
ти равен n. Тогда в корне появится второй по величине элемент,
мы изымаем его, заменяя бесконечностью и корректируя дерево. Так
постепенно мы изымем все элементы в порядке возрастания, пока в
корне не останется бесконечность.
При записи этого алгоритма полезно нумеровать кружочки чис-
лами 1, 2, ...: сыновьями кружка номер n являются кружки 2*n и
2*n+1. Подробное изложение этого алгоритма мы опустим, поскольку
мы изложим более эффективный вариант, не требующий дополни-
тельной памяти, кроме конечного числа переменных (в дополнении к
сортируемому массиву).
Мы будем записывать сортируемые числа во всех вершинах де-
рева, а не только на верхнем уровне. Пусть x[1]..x[n] - массив,
подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о
числе x[i] мы будем говорить как о числе, стоящем в вершине i. В
процессе сортировки количество вершин дерева будет сокращаться.
Число вершин текущего дерева будем хранить в переменной k. Таким
образом, в процессе работы алгоритма массив x[1]..x[n] делится
на две части: в x[1]..x[k] хранятся числа на дереве, а в x[k+1]
.. x[n] хранится уже отсортированная в порядке возрастания часть
массива - элементы, уже занявшие свое законное место.
На каждом шаге алгоритм будет изымать максимальный элемент
дерева и помещать его в отсортированную часть, на освободившееся
в результате сокращения дерева место.
Договоримся о терминологии. Вершинами дерева считаются чис-
ла от 1 до текущего значения переменной k. У каждой вершины s
могут быть сыновья 2s и 2s+1. Если оба этих числа больше k, то
сыновей нет; такая вершина называется листом. Если 2s=k, то вер-
шина s имеет ровно одного сына (2s).
Для каждого s из 1..k рассмотрим "поддерево" с корнем в s:
оно содержит вершину s и всех ее потомков (сыновей, сыновей сы-
новей и т.д. - до тех пор, пока мы не выйдем из отрезка 1..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.
(Эта задача приведена в главе о массивах.) Теперь осталось от-
сортировать первую и третью части: это делается тем же способом.
Время работы этого алгоритма - случайная величина; можно дока-
зать, что в среднем он работает не больше C*n*log n. На практике
- он один из самых быстрых. (Мы еще вернемся к нему, приведя его
рекурсивную и нерекурсивную реализации.)
Наконец, отметим, что сортировка за время порядка C*n*log n
может быть выполнена с помощью техники сбалансированных деревьев
(см. главу 12), однако программы тут сложнее и константа C до-
вольно велика.
4.3. Применения сортировки.
4.3.1. Найти количество различных чисел среди элементов
данного массива. Число действий порядка n*log n. (Эта задача уже
была в главе о массивах.)
Решение. Отсортировать числа, а затем посчитать количество
различных, просматривая элементы массива по порядку.
4.3.2. Дано n отрезков [a[i], b[i]] на прямой (i=1..n).
Найти максимальное k, для которого существует точка прямой, пок-
рытая k отрезками ("максимальное число слоев"). Число действий -
порядка n*log n.
Решение. Упорядочим все левые и правые концы отрезков вмес-
те (при этом левый конец считается меньше правого конца, распо-
ложеннного в той же точке прямой). Далее двигаемся слева напра-
во, считая число слоев. Встреченный левый конец увеличивает
число слоев на 1, правый - уменьшает. Отметим, что примыкающие
друг к другу отрезки обрабатываются правильно: сначала идет ле-
вый конец (правого отрезка), а затем - правый (левого отрезка).
4.3.3. Дано n точек на плоскости. Указать (n-1)-звенную не-
самопересекающуюся незамкнутую ломаную, проходящую через все эти
точки. (Соседним отрезкам ломаной разрешается лежать на одной
прямой.) Число действий порядка n*log n.
Решение. Упорядочим точки по x-координате, а при равных
x-координатах - по y-координате. В таком порядке и можно прово-
дить ломаную.
4.3.4. Та же задача, если ломаная должна быть замкнутой.
