.. 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. Та же задача, если ломаная должна быть замкнутой.
Решение. Возьмем самую левую точку (т.е. точку с наименьшей
x-координатой) и проведем из нее лучи во все остальные точки.
Теперь упорядочим эти лучи, а точки на одном луче поместим в по-
рядке увеличения расстояния от начала луча.
4.3.5. Дано n точек на плоскости. Построить их выпуклую
оболочку - минимальную выпуклую фигуру, их содержащую. (Форму
выпуклой оболочки примет резиновое колечко, если его натянуть на
гвозди, вбитые в точках.) Число операций не более n*log n.
Указание. Упорядочим точки - годится любой из порядков, ис-
пользованных в двух предыдущих задачах. Затем, рассматривая точ-
ки по очереди, будем строить выпуклую оболочку уже рассмотренных
точек. (Для хранения выпуклой оболочки полезно использовать дек,
см. главу 6 о типах данных.)
4.4. Нижние оценки для числа сравнений при сортировке.
Пусть имеется n различных по весу камней и весы, которые
позволяют за одно взвешивание определить, какой из двух выбран-
ных нами камней тяжелее. (В программистских терминах: мы имеем
доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить
камни по весу, сделав как можно меньше взвешиваний (вызовов
функции "тяжелее").
Разумеется, число взвешиваний зависит не только от выбранно-
го нами алгоритма, но и от того, как оказались расположены кам-
ни. Сложностью алгоритма назовем число взвешиваний при наихудшем
расположении камней.
4.4.1. Доказать, что сложность любого алгоритма сортировки n
камней не меньше log (n!). (Логарифм берется по основанию 2, n!
- произведение чисел 1..n.)
Решение. Пусть имеется алгоритм сложности не более d. Для
каждого из n! возможных расположений камней запротоколируем ре-
зультаты взвешиваний (обращений к функции "тяжелее"); их можно
записать в виде последовательности из не более чем d нулей и
единиц. Для единообразия дополним последовательность нулями,
чтобы ее длина стала равной d. Тем самым у нас имеется n! после-
довательностей из d нулей и единиц. Все эти последовательности
разные - иначе наш алгоритм дал бы одинаковые ответы для разных
порядков (и один из ответов был бы неправильным). Получаем, что
2 в степени d не меньше n! - что и требовалось доказать.
Другой способ объяснить то же самое - рассмотреть дерево
вариантов, возникающее в ходе выполнения алгоритма, и сослаться
на то, что дерево высоты d не может иметь более (2 в степени d)
листьев.
Это рассуждение показывает, что любой алгоритм сортировки,
использующий только сравнения элементов массива и их перестанов-
ки, требует не менее C*n*log n действий, так что наши алгоритмы
близки к оптимальным. Однако алгоритм сортировки, использующий
другие операции, может действовать быстрее. Вот один из приме-
ров.
4.4.2. Имеется массив целых чисел a[1]..a[n], причем все
числа неотрицательны и не превосходят m. Отсортировать этот мас-
сив; число действий порядка m+n.
Решение. Для каждого числа от 0 до m подсчитываем, сколько
раз оно встречается в массиве. После этого исходный массив можно
стереть и заполнить заново в порядке возрастания, используя све-
дения о кратности каждого числа.
Отметим также, что этот алгоритм не переставляет числа в масси-
ве, как большинство других, а "записывает их туда заново".
Есть также метод сортировки, в котором последовательно проводится
ряд "частичных сортировок" по отдельным битам. Начнём с такой
задачи:
4.4.3. В массиве a[1]..a[n] целых чисел переставить элемен-
ты так, чтобы чётные шли перед нечётными (не меняя взаимный по-
рядок в каждой из групп).
Решение. Сначала спишем (во вспомогательный массив) все
чётные, а потом - все нечётные.
4.4.4. Имеется массив из n чисел от 0 до (2 в степени k) -
1, каждое из которых мы будем рассматривать как k-битовое слово.
Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вмес-
то сравнений, отсортировать все числа за время порядка n*k.
Решение. Отсортируем числа по последнему биту (см. предыду-
щую задачу), затем по предпоследнему и так далее. В результате
они будут отсортированы. В самом деле, индукцией по i легко до-
казать, что после i шагов любые два числа, отличающиеся только в
i последних битах, идут в правильном порядке. (Вариант: после i
шагов i-битовые концы чисел идут в правильном порядке.)
Аналогичный алгоритм может быть применен для m-ичной систе-
мы счисления вместо двоичной. При этом полезна такая вспомога-
тельная задача:
4.4.5. Даны n чисел и функция f, принимающая (на них) зна-
чения 1..m. Требуется переставить числа в таком порядке, чтобы
значения функции f не убывали (сохраняя притом порядок внутри
