Решение 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. Та же задача, если ломаная должна быть замкнутой.
Решение. Возьмем самую левую точку (т.е. точку с наименьшей
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! - что и требовалось доказать.
Другой способ объяснить то же самое - рассмотреть дерево
вариантов, возникающее в ходе выполнения алгоритма, и сослаться
