Практикум по методам построения алгоритмов

Сортировка

Разбить на страницы
Показывать лекцию целиком

4.1. Квадратичные алгоритмы

4.1.1. Пусть $${a[1]},\ldots,{a[n]}$$ - целые числа. Требуется построить массив $${b[1]},\ldots,{b[n]}$$, содержащий те же числа, для которого $${b[1]}\le\ldots\le{b[n]}$$.

Замечание. Среди чисел $${a[1]}\ldots{a[n]}$$ могут быть равные. Требуется, чтобы каждое целое число входило в $${b[1]}\ldots{b[n]}$$ столько же раз, сколько и в $${a[1]}\ldots{a[n]}$$.

Решение. Удобно считать, что числа $${a[1]}\ldots{a[n]}$$ и $${b[1]}\ldots{b[n]}$$ представляют собой начальное и конечное значения массива x. Требование " a и b содержат одни и те же числа" будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.

k := 0;
{k наименьших элементов массива установлены на свои места}
while k <> n do begin
| s := k + 1; t := k + 1;
| {x[s] - наименьший среди x[k+1]...x[t] }
| while t<>n do begin
| | t := t + 1;
| | if x[t] < x[s] then begin
| | | s := t;
| | end;
| end;
| {x[s] - наименьший среди x[k+1]..x[n] }
| ... переставить x[s] и x[k+1];
| k := k + 1;
end;

4.1.2. Дать другое решение задачи сортировки, использующее инвариант "первые k элементов упорядочены" ( $${x[1]}\le\ldots\le{x[k]}$$ ).

Решение.

k:=1;
{первые k элементов упорядочены}
while k <> n do begin
| t := k+1;
| {k+1-ый элемент продвигается к началу, пока не займет
|   надлежащего места, t - его текущий номер}
| while (t > 1) and (x[t] < x[t-1]) do begin
| | ...поменять x[t-1] и x[t];
| | t := t - 1;
| end;
end;

Замечание. Дефект программы: при ложном выражении (t>1) проверка $${x[t]}<{x[t-1]}$$ требует несуществующего значения x[0].

Оба предложенных решения требуют числа действий, пропорционального $${n}^2$$. Существуют более эффективные алгоритмы.

4.2. Алгоритмы порядка n log n

4.2.1. Предложить алгоритм сортировки за время $$\text{n log n}$$ (число операций при сортировке $$n$$ элементов не больше $$\text{Cn log n}$$ для некоторого $$C$$ и для всех $$n$$ ).

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

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

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

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

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

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

Тогда преобразование 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;

(Любители языка C написали бы в этом случае b[++s0]=x[++p0] и b[++s0]=x[++q0].)

Первое действие (взятие элемента из первого отрезка) может производиться при одновременном выполнении двух условий:

(1) первый отрезок не кончился ( $${p0}<{q}$$ );

(2) второй отрезок кончился ( $${q0}={r}$$ ) или не кончился, но элемент в нем не меньше очередного элемента первого отрезка [ $$({q0} < {r}$$ ) и ( $${x[p0+1]}\le{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 (сортировка деревом).

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

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

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

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

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

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

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

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

Заметим, что истинность утверждения " s -поддерево регулярно" зависит не только от s, но от текущего значения k.

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

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 имеет тип $$\text{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.) Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает не больше $$\text{Cn log n}$$. На практике - он один из самых быстрых. (Мы еще вернемся к нему, приведя его рекурсивную и нерекурсивную реализации.)

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

4.3. Применения сортировки.

4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка $$\text{n log n}$$. (Эта задача уже была в лекции 1.)

Решение. Отсортировать числа, а затем посчитать количество различных, просматривая элементы массива по порядку.

4.3.2. Дано n отрезков $$[{a[i]},{b[i]}]$$ на прямой ( $${i}={1}\ldots{n}$$ ). Найти максимальное k, для которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Число действий - порядка $${n} log{n}$$.

Решение. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка).

4.3.3. Дано $$n$$ точек на плоскости. Указать $$(n-1)$$ -звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Число действий порядка $$\text{n log n}$$.

Решение. Упорядочим точки по $$x$$ -координате, а при равных $$x$$ -координатах - по $$y$$ -координате. В таком порядке и можно проводить ломаную.

4.3.4. Та же задача, если ломаная должна быть замкнутой.

Решение. Возьмем самую левую точку (то есть точку с наименьшей $$x$$ -координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу.

4.3.5. Дано $$n$$ точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.) Число операций не более $$\text{n log n}$$.

Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек, см. лекцию 6. Впрочем, при упорядочении точек по углам это излишне.)

4.4. Нижние оценки для числа сравнений при сортировке

Пусть имеется $$n$$ различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить камни по весу, сделав как можно меньше взвешиваний (вызовов функции тяжелее ).

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

4.4.1. Доказать, что сложность произвольного алгоритма сортировки $$n$$ камней не меньше $$log_2 n$$! (где $$n!=1\cdot2\cdot\ldots \cdot n$$ ).

Решение. Пусть имеется алгоритм сложности не более $$d$$. Для каждого из $$n$$! возможных расположений камней запротоколируем результаты взвешиваний (обращений к функции тяжелее ); их можно записать в виде последовательности из не более чем $$d$$ нулей и единиц. Для единообразия дополним последовательность нулями, чтобы ее длина стала равной $$d$$. Тем самым у нас имеется $$n$$! последовательностей из $$d$$ нулей и единиц. Все эти последовательности разные - иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что $$2^d \ge n$$! - что и требовалось доказать.

Другой способ объяснить то же самое - рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты $$d$$ не может иметь более $$2^d$$ листьев.

Несложно заметить, что $$log_2 n!\ge \text{cn log n}$$ при подходящем $$c>0$$, поскольку в сумме$$log n! = log 1 + log 2 + log 3 + \ldots + log n$$ вторая половина слагаемых не меньше $$log_2 (n/2) = log_2 n -1$$ каждое.

Тем самым любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее $$\text{Cn log n}$$ действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать и быстрее. Вот один из примеров.

4.4.2. Имеется массив целых чисел $${a[1]}\ldots{a[n]}$$, причем все числа неотрицательны и не превосходят m. Отсортировать этот массив; число действий порядка $${m}+{n}$$.

Решение. Для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно стереть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа.

Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а "записывает их туда заново".

Есть также метод сортировки, в котором последовательно проводится ряд "частичных сортировок" по отдельным битам. Начнем с такой задачи.

4.4.3. В массиве $${a[1]}\ldots{a[n]}$$ целых чисел переставить элементы так, чтобы четные числа шли перед нечетными (не меняя взаимный порядок в каждой из групп).

Решение. Сначала спишем (во вспомогательный массив) все четные, а потом - все нечетные.

4.4.4. Имеется массив из $$n$$ чисел от $$0$$ до $$2^k-1$$, каждое из которых мы будем рассматривать как $$k$$ -битовое слово из нулей и единиц. Используя проверки " $$i$$ -ый бит равен $$0$$ " и " $$i$$ -ый бит равен $$1$$ " вместо сравнений, отсортировать все числа за время порядка $$nk$$.

Решение. Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по $$i$$ легко доказать, что после $$i$$ шагов любые два числа, отличающиеся только в $$i$$ последних битах, идут в правильном порядке. (Вариант: после $$i$$ шагов $$i$$ -битовые концы чисел идут в правильном порядке.)

Аналогичный алгоритм может быть применен для $$m$$ -ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:

4.4.5. Даны $$n$$ чисел и функция $$f$$, принимающая (на них) значения $$1\ldots m$$. Требуется переставить числа в таком порядке, чтобы значения функции $$f$$ не убывали (сохраняя порядок для чисел с равными значениями $$f$$ ). Число действий порядка $$m+n$$.

Указание. Завести $$m$$ списков суммарной длины $$n$$ (как это сделать, смотри в лекции 6 о типах данных) и помещать в $$i$$ -ый список числа, для которых значение функции $$f$$ равно $$i$$. Вариант: посчитать для всех $$i$$, сколько имеется чисел $$x$$ с $$f(x)=i$$, после чего легко определить, с какого места нужно начинать размещать числа $$x$$ с $$f(x)=i$$.

4.4.6. Даны $$n$$ целых чисел в диапазоне от $$1$$ до $$n^2$$. Как отсортировать их, сделав порядка $$n$$ действий?

4.5. Родственные сортировке задачи

4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого тяжелого из $$n$$ камней?

Решение. Очевидный алгоритм с инвариантом "найден самый тяжелый камень среди первых $$i$$ " требует $$n-1$$ сравнений. Алгоритма меньшей сложности нет. Это вытекает из следующего более сильного утверждения.

4.5.2. Эксперт хочет убедить суд, что данный камень - самый тяжелый среди $$n$$ камней, сделав менее $$n-1$$ взвешиваний. Доказать, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.)

Решение. Изобразим камни точками, а взвешивания - линиями между ними. Получим граф с $$n$$ вершинами и менее чем $$n-1$$ ребрами. Такой граф несвязен (добавление каждого следующего ребра уменьшает число связных компонент не более чем на $$1$$ ). Поэтому суд ничего не знает относительно соотношения весов камней в различных связных компонентах и может допустить, что самый тяжелый камень - в любой из них.

Более простое объяснение: будем следить за тем, сколько камней к данному моменту не "проиграли" (то есть не оказались легче других). Вначале их $$n$$ ; при каждом взвешивании проигрывает только один камень, а если есть двое не проигравших никому, любой из них может (с точки зрения суда) оказаться самым тяжелым.

Разница между этой задачей и предыдущей: в этой задаче мы доказываем, что $$n-2$$ взвешиваний не достаточно не только для нахождения самого тяжелого, но даже для того, чтобы убедиться, что данный камень является таковым - если предположительный ответ известен. (В случае сортировки, зная предположительный ответ, мы можем убедиться в его правильности, сделав всего $$n-1$$ сравнений - каждый сравниваем со следующим по весу. Напомним, что сортировка требует в худшем случае значительно больше сравнений.)

4.5.3. Доказать, что можно найти самый легкий и самый тяжелый из $$2n$$ камней (одновременно), сделав $$3n-2$$ взвешиваний.

Решение. Разобьем камни произвольным образом на $$n$$ пар и сравним камни в каждой паре ( $$n$$ взвешиваний). Отложим отдельно "победителей" (более тяжелых в своей паре) и "проигравших" (более легких). Ясно, что самый легкий камень надо искать среди проигравших ( $$n-1$$ сравнений), а самый тяжелый - среди победителей (еще $$n-1$$ сравнений).

4.5.4. Доказать, что не существует алгоритма, позволяющего гарантированно найти самый легкий и самый тяжелый среди $$2n$$ камней (одновременно), сделав менее $$3n-2$$ взвешиваний.

Решение. Пусть такой алгоритм существует. Наблюдая за его применением к какой-то группе из $$2n$$ камней, мы будем следить за четырьмя параметрами. А именно, мы будем смотреть, сколько камней

(a) кому-то уже проиграли, а у кого-то уже выиграли;

(b) кому-то уже проиграли, но еще ни у кого не выиграли;

(c) у кого-то уже выиграли, но еще никому не проиграли;

(d) ни у кого не выиграли и никому не проиграли (то есть ни с кем не сравнивались).

(Напомним, что выигравшим в сравнении мы считаем более тяжелый камень.) Камни типа (a), очевидно, не могут уже оказаться ни самыми легкими, ни самыми тяжелыми, каковы бы ни были результаты дальнейших сравнений. Любой камень типа (b) имеет шанс оказаться самым легким (в самом деле, его можно произвольно облегчить, не меняя результатов уже выполненных сравнений), но уже не может быть самым тяжелым; для камней типа (c) наоборот. Наконец, любой камень типа (d) может быть и самым легким, и самым тяжелым.

Обозначим через $$a,b,c,d$$ количества камней в соответствующих категориях и проследим, как меняются эти параметры при очередном сравнении (в зависимости от того, камни какого типа сравниваются и с каким результатом).

сравнение a b c d b+c+(3/2)d
a-a 0 0 0 0 0 
a>b
a<b
 
0
+1
 
0
-1
 
0
0
 
0
0
 
0
-1
 
a<c
a>c
 
0
+1
 
+1
0
 
0
-1
 
-1
0
 
0
-1
 
a>d
a<d
 
0
0
 
+1
0
 
0
+1
 
-1
-1
 
-1/2
-1/2
b-b +1 -1 0 0 -1 
b<c
b>c
 
0
+2
 
0
-1
 
0
-1
 
0
0
 
0
-2
 
b<d
b>d
 
0
+1
 
0
0
 
+1
0
 
-1
-1
 
-1/2
-3/2
c-c +1 0 -1 0 -1 
c<d
c>d
 
+1
0
 
0
+1
 
0
0
 
-1
-1
 
-3/2
-1/2
d-d 0 +1 +1 -2 -1

Последний столбец таблицы показывает, как меняется величина $$\lessmskips{1mu}s=b+c+(3/2)d$$ (которую можно рассматривать в качестве меры "оставшейся работы": камень, про который не известно ничего, с точки зрения этой меры в полтора раза сложнее камня, для которого есть односторонняя оценка). Изначально $$s=3n$$, а в конце $$s=2$$ (про все камни, кроме двух, известно, что они относятся к категории (a)). Из таблицы видно, что при любом взвешивании есть "неудачный исход", при котором $$s$$ уменьшается не более чем на единицу. Такие исходы действительно возможны (не противоречат результатам предыдущих взвешиваний): при сравнении $$b$$ -камня и $$c$$ -камня может оказаться, что $$c$$ -камень тяжелее (его вес не ограничен сверху предыдущими взвешиваниями), а при сравнении c участием $$d$$ -камня результат может быть любым, поскольку про $$d$$ -камень ничего не известно. (Кроме того, можно заметить, что один из исходов взвешивания невозможен, то это взвешивание вообще излишне и его можно не делать.) А если исходы всех взвешиваний неудачны, то уменьшение $$s$$ с $$3n$$ до $$2$$ потребует как минимум $$3n-2$$ взвешиваний, что и требовалось доказать.

4.5.5. Дано $$n$$ различных по весу камней. Найти самый тяжелый и второй по весу камни, сделав не более $$n+\lceil log_2 n\rceil-2$$ взвешиваний ( $$\lceil log_2 n\rceil$$ - наименьшее целое $$k$$, при котором $$2^k \ge n$$ ).

Решение. Сначала найдем победителя (самый тяжелый камень), а потом будем искать второй по весу. Ясно, что второго можно искать лишь среди тех, кто проиграл лично победителю (проигравшие кому-то еще легче сразу двух камней). Если определять победителя в турнире по олимпийской системе (все делятся на пары, проигравшие выбывают, потом снова делятся на пары и так далее), то для $$2^k$$ участников понадобится $$k$$ раундов, а для $$n$$ участников - $$\lceil log_2 n\rceil$$ раундов. В каждой игре турнира выбывает один участник, поэтому всего будет $$n-1$$ игр для определения победителя и еще $$\lceil log_2n\rceil-1$$ в турнире за второе место среди проигравших победителю.

4.5.6. Доказать, что никакой алгоритм нахождения самого тяжелого и второго по весу среди $$n$$ камней не может гарантированно сделать это менее чем за $$n+\lceil log_2 n\rceil -2$$ взвешиваний.

Решение. Пусть дан такой алгоритм. В каждый момент его исполнения рассмотрим число $$k_i$$ камней-участников, проигравших не менее $$i$$ игр-сравнений. (Косвенные проигрыши - если $$a$$ проиграл $$b$$, а $$b$$ проиграл $$c$$, - не учитываются.) Легко понять, что сумма $$k_i$$ по всем $$i$$ равна числу игр, так как после каждой игры одно из $$k_i$$ увеличивается на единицу.

Поэтому достаточно показать, что каков бы ни был алгоритм, при неудачных для него результатах игр будет выполнено неравенство $$k_1+k_2 \ge n + \lceil log_2 n\rceil -2$$. Будем называть " лидерами " тех участников, которые еще никому не проиграли. В начале их $$n$$, а в конце остается только один лидер (поскольку любой из лидеров может быть победителем). Поэтому $$k_1 \ge n-1$$ (все игроки, кроме одного, кому-то проиграли). Объясним, как надо выбирать результаты матчей, чтобы добиться неравенства $$k_2\ge \lceil log_2n\rceil -2$$. Результат встречи двух не-лидеров может быть выбран любым. Если лидер встречается с не-лидером, то выигрывает лидер. При встрече двух лидеров выигрывает более опытный, то есть тот, кто выиграл к этому моменту больше игр (при равенстве - любой).

Чтобы доказать, что в этом случае выполнено искомое неравенство на $$k_2$$, введем отношения подчинения, считая при этом, что каждый игрок в любой момент игры подчинен ровно одному лидеру. В начале каждый сам себе лидер и подчинен только себе. При встрече лидера с не-лидером (или двух не-лидеров) подчинение не меняется; при встрече двух лидеров проигравший и все его подчиненные переподчиняются выигравшему.

Легко доказать по индукции, что если лидер выиграл $$k$$ игр, то группа его подчиненных (включая его самого) содержит не более $$2^k$$ человек. Вначале $$k=0$$ и в его группе только он сам. Если лидер выиграл $$k$$ игр и побеждает лидера, выигравшего не более $$k$$ игр, то в каждой из групп не более $$2^k$$ игроков, а в объединении не более $$2^{k+1}$$ игроков.

Следовательно, по окончании турнира лидер выиграл не менее $$\lceil log_2 n\rceil$$ игр, поскольку в его группе все $$n$$ игроков. Все побежденные им, кроме второго по силе игрока, проиграли еще кому-то (иначе почему мы уверены, что они не вторые по силе?). Отсюда и получается требуемая оценка на $$k_2$$.

4.5.7. Доказать, что оценка предыдущей задачи остается в силе, если требуется найти лишь второй по весу камень, а самый тяжелый искать не обязательно.

Указание. Если по окончанию турнира определился второй по силе игрок, то он кому-то проиграл (откуда мы знаем иначе, что он не первый?), и тем самым известен и победитель.

4.5.8. Дано $$n$$ различных по весу камней и число $$k$$ (от $$1$$ до $$n$$ ). Требуется найти $$k$$ -ый по весу камень, сделав не более $$Cn$$ взвешиваний, где $$C$$ - некоторая константа, не зависящая от $$k$$ и $$n$$.

Замечание. Сортировка позволяет сделать это за $$\text{Cn log n}$$ взвешиваний. Указание к этой (трудной) задаче приведено в лекции про рекурсию.

Следующая задача имеет неожиданно простое решение.

4.5.9. Имеется $$n$$ одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более $$n/2$$ ) одинаковых. Сделав не более $$n$$ взвешиваний, найти хотя бы один камень из этого большинства. (Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству.)

Указание. Если найдены два различных камня, то их оба можно выбросить - хотя бы один из них плохой и большинство останется большинством.

Решение. Программа просматривает камни по очереди, храня в переменной i число просмотренных камней. (Считаем камни пронумерованными от 1 до n.) Помимо этого программа хранит номер "текущего кандидата" c и его "кратность" k. Смысл этих названий объясняется инвариантом (И):

если к непросмотренным камням (с номерами i+1...n ) добавили бы k копий c -го камня, то наиболее частым среди них был бы такой же камень, что и для исходного массива.

Получаем такую программу:

k:=0; i:=0;
{(И)}
while i<>n do begin
| if k=0 then begin
| | k:=1; c:=i+1; i:=i+1;
| end else if (i+1-ый камень одинаков с c-ым) then begin
| | i:=i+1; k:=k+1;
| |  {заменяем материальный камень идеальным}
| end else begin
| | i:=i+1; k:=k-1;
| | {выкидываем один материальный и один идеальный камень}
| end;
end;
искомым является c-ый камень

Замечание. Поскольку во всех трех вариантах выбора стоит команда i:=i+1, ее можно вынести наружу.

Заметим также, что эта программа гарантирует отыскание наиболее частого камня, лишь если он составляет большинство.

Следующая задача не имеет на первый взгляд никакого отношения к сортировке.

4.5.10. Имеется квадратная таблица a[1..n,1..n]. Известно, что для некоторого i строка с номером i заполнена одними нулями, а столбец с номером i - одними единицами (за исключением их пересечения на диагонали, где стоит неизвестно что). Найти такое i (оно, очевидно, единственно). Число действий порядка n. (Заметим, что это существенно меньше числа элементов в таблице.)

Указание. Рассмотрите a[i][j] как результат "сравнения" i с j и вспомните, что самый тяжелый из n камней может быть найден за n сравнений. (Заметим, что таблица может не быть "транзитивной", но все равно при "сравнении" двух элементов один из них отпадает.)

Страницы:

4.1. Квадратичные алгоритмы

4.1.1. Пусть $${a[1]},\ldots,{a[n]}$$ - целые числа. Требуется построить массив $${b[1]},\ldots,{b[n]}$$, содержащий те же числа, для которого $${b[1]}\le\ldots\le{b[n]}$$.

Замечание. Среди чисел $${a[1]}\ldots{a[n]}$$ могут быть равные. Требуется, чтобы каждое целое число входило в $${b[1]}\ldots{b[n]}$$ столько же раз, сколько и в $${a[1]}\ldots{a[n]}$$.

Решение. Удобно считать, что числа $${a[1]}\ldots{a[n]}$$ и $${b[1]}\ldots{b[n]}$$ представляют собой начальное и конечное значения массива x. Требование " a и b содержат одни и те же числа" будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.

k := 0;
{k наименьших элементов массива установлены на свои места}
while k <> n do begin
| s := k + 1; t := k + 1;
| {x[s] - наименьший среди x[k+1]...x[t] }
| while t<>n do begin
| | t := t + 1;
| | if x[t] < x[s] then begin
| | | s := t;
| | end;
| end;
| {x[s] - наименьший среди x[k+1]..x[n] }
| ... переставить x[s] и x[k+1];
| k := k + 1;
end;

4.1.2. Дать другое решение задачи сортировки, использующее инвариант "первые k элементов упорядочены" ( $${x[1]}\le\ldots\le{x[k]}$$ ).

Решение.

k:=1;
{первые k элементов упорядочены}
while k <> n do begin
| t := k+1;
| {k+1-ый элемент продвигается к началу, пока не займет
|   надлежащего места, t - его текущий номер}
| while (t > 1) and (x[t] < x[t-1]) do begin
| | ...поменять x[t-1] и x[t];
| | t := t - 1;
| end;
end;

Замечание. Дефект программы: при ложном выражении (t>1) проверка $${x[t]}<{x[t-1]}$$ требует несуществующего значения x[0].

Оба предложенных решения требуют числа действий, пропорционального $${n}^2$$. Существуют более эффективные алгоритмы.

4.2. Алгоритмы порядка n log n

4.2.1. Предложить алгоритм сортировки за время $$\text{n log n}$$ (число операций при сортировке $$n$$ элементов не больше $$\text{Cn log n}$$ для некоторого $$C$$ и для всех $$n$$ ).

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

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

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

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

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

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

Тогда преобразование 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;

(Любители языка C написали бы в этом случае b[++s0]=x[++p0] и b[++s0]=x[++q0].)

Первое действие (взятие элемента из первого отрезка) может производиться при одновременном выполнении двух условий:

(1) первый отрезок не кончился ( $${p0}<{q}$$ );

(2) второй отрезок кончился ( $${q0}={r}$$ ) или не кончился, но элемент в нем не меньше очередного элемента первого отрезка [ $$({q0} < {r}$$ ) и ( $${x[p0+1]}\le{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 (сортировка деревом).

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

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

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

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

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

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

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

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

Заметим, что истинность утверждения " s -поддерево регулярно" зависит не только от s, но от текущего значения k.

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

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 имеет тип $$\text{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.) Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает не больше $$\text{Cn log n}$$. На практике - он один из самых быстрых. (Мы еще вернемся к нему, приведя его рекурсивную и нерекурсивную реализации.)

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

4.3. Применения сортировки.

4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка $$\text{n log n}$$. (Эта задача уже была в лекции 1.)

Решение. Отсортировать числа, а затем посчитать количество различных, просматривая элементы массива по порядку.

4.3.2. Дано n отрезков $$[{a[i]},{b[i]}]$$ на прямой ( $${i}={1}\ldots{n}$$ ). Найти максимальное k, для которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Число действий - порядка $${n} log{n}$$.

Решение. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка).

4.3.3. Дано $$n$$ точек на плоскости. Указать $$(n-1)$$ -звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Число действий порядка $$\text{n log n}$$.

Решение. Упорядочим точки по $$x$$ -координате, а при равных $$x$$ -координатах - по $$y$$ -координате. В таком порядке и можно проводить ломаную.

4.3.4. Та же задача, если ломаная должна быть замкнутой.

Решение. Возьмем самую левую точку (то есть точку с наименьшей $$x$$ -координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу.

4.3.5. Дано $$n$$ точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.) Число операций не более $$\text{n log n}$$.

Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек, см. лекцию 6. Впрочем, при упорядочении точек по углам это излишне.)

4.4. Нижние оценки для числа сравнений при сортировке

Пусть имеется $$n$$ различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить камни по весу, сделав как можно меньше взвешиваний (вызовов функции тяжелее ).

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

4.4.1. Доказать, что сложность произвольного алгоритма сортировки $$n$$ камней не меньше $$log_2 n$$! (где $$n!=1\cdot2\cdot\ldots \cdot n$$ ).

Решение. Пусть имеется алгоритм сложности не более $$d$$. Для каждого из $$n$$! возможных расположений камней запротоколируем результаты взвешиваний (обращений к функции тяжелее ); их можно записать в виде последовательности из не более чем $$d$$ нулей и единиц. Для единообразия дополним последовательность нулями, чтобы ее длина стала равной $$d$$. Тем самым у нас имеется $$n$$! последовательностей из $$d$$ нулей и единиц. Все эти последовательности разные - иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что $$2^d \ge n$$! - что и требовалось доказать.

Другой способ объяснить то же самое - рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты $$d$$ не может иметь более $$2^d$$ листьев.

Несложно заметить, что $$log_2 n!\ge \text{cn log n}$$ при подходящем $$c>0$$, поскольку в сумме$$log n! = log 1 + log 2 + log 3 + \ldots + log n$$ вторая половина слагаемых не меньше $$log_2 (n/2) = log_2 n -1$$ каждое.

Тем самым любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее $$\text{Cn log n}$$ действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать и быстрее. Вот один из примеров.

4.4.2. Имеется массив целых чисел $${a[1]}\ldots{a[n]}$$, причем все числа неотрицательны и не превосходят m. Отсортировать этот массив; число действий порядка $${m}+{n}$$.

Решение. Для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно стереть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа.

Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а "записывает их туда заново".

Есть также метод сортировки, в котором последовательно проводится ряд "частичных сортировок" по отдельным битам. Начнем с такой задачи.

4.4.3. В массиве $${a[1]}\ldots{a[n]}$$ целых чисел переставить элементы так, чтобы четные числа шли перед нечетными (не меняя взаимный порядок в каждой из групп).

Решение. Сначала спишем (во вспомогательный массив) все четные, а потом - все нечетные.

4.4.4. Имеется массив из $$n$$ чисел от $$0$$ до $$2^k-1$$, каждое из которых мы будем рассматривать как $$k$$ -битовое слово из нулей и единиц. Используя проверки " $$i$$ -ый бит равен $$0$$ " и " $$i$$ -ый бит равен $$1$$ " вместо сравнений, отсортировать все числа за время порядка $$nk$$.

Решение. Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по $$i$$ легко доказать, что после $$i$$ шагов любые два числа, отличающиеся только в $$i$$ последних битах, идут в правильном порядке. (Вариант: после $$i$$ шагов $$i$$ -битовые концы чисел идут в правильном порядке.)

Аналогичный алгоритм может быть применен для $$m$$ -ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:

4.4.5. Даны $$n$$ чисел и функция $$f$$, принимающая (на них) значения $$1\ldots m$$. Требуется переставить числа в таком порядке, чтобы значения функции $$f$$ не убывали (сохраняя порядок для чисел с равными значениями $$f$$ ). Число действий порядка $$m+n$$.

Указание. Завести $$m$$ списков суммарной длины $$n$$ (как это сделать, смотри в лекции 6 о типах данных) и помещать в $$i$$ -ый список числа, для которых значение функции $$f$$ равно $$i$$. Вариант: посчитать для всех $$i$$, сколько имеется чисел $$x$$ с $$f(x)=i$$, после чего легко определить, с какого места нужно начинать размещать числа $$x$$ с $$f(x)=i$$.

4.4.6. Даны $$n$$ целых чисел в диапазоне от $$1$$ до $$n^2$$. Как отсортировать их, сделав порядка $$n$$ действий?

4.5. Родственные сортировке задачи

4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого тяжелого из $$n$$ камней?

Решение. Очевидный алгоритм с инвариантом "найден самый тяжелый камень среди первых $$i$$ " требует $$n-1$$ сравнений. Алгоритма меньшей сложности нет. Это вытекает из следующего более сильного утверждения.

4.5.2. Эксперт хочет убедить суд, что данный камень - самый тяжелый среди $$n$$ камней, сделав менее $$n-1$$ взвешиваний. Доказать, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.)

Решение. Изобразим камни точками, а взвешивания - линиями между ними. Получим граф с $$n$$ вершинами и менее чем $$n-1$$ ребрами. Такой граф несвязен (добавление каждого следующего ребра уменьшает число связных компонент не более чем на $$1$$ ). Поэтому суд ничего не знает относительно соотношения весов камней в различных связных компонентах и может допустить, что самый тяжелый камень - в любой из них.

Более простое объяснение: будем следить за тем, сколько камней к данному моменту не "проиграли" (то есть не оказались легче других). Вначале их $$n$$ ; при каждом взвешивании проигрывает только один камень, а если есть двое не проигравших никому, любой из них может (с точки зрения суда) оказаться самым тяжелым.

Разница между этой задачей и предыдущей: в этой задаче мы доказываем, что $$n-2$$ взвешиваний не достаточно не только для нахождения самого тяжелого, но даже для того, чтобы убедиться, что данный камень является таковым - если предположительный ответ известен. (В случае сортировки, зная предположительный ответ, мы можем убедиться в его правильности, сделав всего $$n-1$$ сравнений - каждый сравниваем со следующим по весу. Напомним, что сортировка требует в худшем случае значительно больше сравнений.)

4.5.3. Доказать, что можно найти самый легкий и самый тяжелый из $$2n$$ камней (одновременно), сделав $$3n-2$$ взвешиваний.

Решение. Разобьем камни произвольным образом на $$n$$ пар и сравним камни в каждой паре ( $$n$$ взвешиваний). Отложим отдельно "победителей" (более тяжелых в своей паре) и "проигравших" (более легких). Ясно, что самый легкий камень надо искать среди проигравших ( $$n-1$$ сравнений), а самый тяжелый - среди победителей (еще $$n-1$$ сравнений).

4.5.4. Доказать, что не существует алгоритма, позволяющего гарантированно найти самый легкий и самый тяжелый среди $$2n$$ камней (одновременно), сделав менее $$3n-2$$ взвешиваний.

Решение. Пусть такой алгоритм существует. Наблюдая за его применением к какой-то группе из $$2n$$ камней, мы будем следить за четырьмя параметрами. А именно, мы будем смотреть, сколько камней

(a) кому-то уже проиграли, а у кого-то уже выиграли;

(b) кому-то уже проиграли, но еще ни у кого не выиграли;

(c) у кого-то уже выиграли, но еще никому не проиграли;

(d) ни у кого не выиграли и никому не проиграли (то есть ни с кем не сравнивались).

(Напомним, что выигравшим в сравнении мы считаем более тяжелый камень.) Камни типа (a), очевидно, не могут уже оказаться ни самыми легкими, ни самыми тяжелыми, каковы бы ни были результаты дальнейших сравнений. Любой камень типа (b) имеет шанс оказаться самым легким (в самом деле, его можно произвольно облегчить, не меняя результатов уже выполненных сравнений), но уже не может быть самым тяжелым; для камней типа (c) наоборот. Наконец, любой камень типа (d) может быть и самым легким, и самым тяжелым.

Обозначим через $$a,b,c,d$$ количества камней в соответствующих категориях и проследим, как меняются эти параметры при очередном сравнении (в зависимости от того, камни какого типа сравниваются и с каким результатом).

сравнение a b c d b+c+(3/2)d
a-a 0 0 0 0 0 
a>b
a<b
 
0
+1
 
0
-1
 
0
0
 
0
0
 
0
-1
 
a<c
a>c
 
0
+1
 
+1
0
 
0
-1
 
-1
0
 
0
-1
 
a>d
a<d
 
0
0
 
+1
0
 
0
+1
 
-1
-1
 
-1/2
-1/2
b-b +1 -1 0 0 -1 
b<c
b>c
 
0
+2
 
0
-1
 
0
-1
 
0
0
 
0
-2
 
b<d
b>d
 
0
+1
 
0
0
 
+1
0
 
-1
-1
 
-1/2
-3/2
c-c +1 0 -1 0 -1 
c<d
c>d
 
+1
0
 
0
+1
 
0
0
 
-1
-1
 
-3/2
-1/2
d-d 0 +1 +1 -2 -1

Последний столбец таблицы показывает, как меняется величина $$\lessmskips{1mu}s=b+c+(3/2)d$$ (которую можно рассматривать в качестве меры "оставшейся работы": камень, про который не известно ничего, с точки зрения этой меры в полтора раза сложнее камня, для которого есть односторонняя оценка). Изначально $$s=3n$$, а в конце $$s=2$$ (про все камни, кроме двух, известно, что они относятся к категории (a)). Из таблицы видно, что при любом взвешивании есть "неудачный исход", при котором $$s$$ уменьшается не более чем на единицу. Такие исходы действительно возможны (не противоречат результатам предыдущих взвешиваний): при сравнении $$b$$ -камня и $$c$$ -камня может оказаться, что $$c$$ -камень тяжелее (его вес не ограничен сверху предыдущими взвешиваниями), а при сравнении c участием $$d$$ -камня результат может быть любым, поскольку про $$d$$ -камень ничего не известно. (Кроме того, можно заметить, что один из исходов взвешивания невозможен, то это взвешивание вообще излишне и его можно не делать.) А если исходы всех взвешиваний неудачны, то уменьшение $$s$$ с $$3n$$ до $$2$$ потребует как минимум $$3n-2$$ взвешиваний, что и требовалось доказать.

4.5.5. Дано $$n$$ различных по весу камней. Найти самый тяжелый и второй по весу камни, сделав не более $$n+\lceil log_2 n\rceil-2$$ взвешиваний ( $$\lceil log_2 n\rceil$$ - наименьшее целое $$k$$, при котором $$2^k \ge n$$ ).

Решение. Сначала найдем победителя (самый тяжелый камень), а потом будем искать второй по весу. Ясно, что второго можно искать лишь среди тех, кто проиграл лично победителю (проигравшие кому-то еще легче сразу двух камней). Если определять победителя в турнире по олимпийской системе (все делятся на пары, проигравшие выбывают, потом снова делятся на пары и так далее), то для $$2^k$$ участников понадобится $$k$$ раундов, а для $$n$$ участников - $$\lceil log_2 n\rceil$$ раундов. В каждой игре турнира выбывает один участник, поэтому всего будет $$n-1$$ игр для определения победителя и еще $$\lceil log_2n\rceil-1$$ в турнире за второе место среди проигравших победителю.

4.5.6. Доказать, что никакой алгоритм нахождения самого тяжелого и второго по весу среди $$n$$ камней не может гарантированно сделать это менее чем за $$n+\lceil log_2 n\rceil -2$$ взвешиваний.

Решение. Пусть дан такой алгоритм. В каждый момент его исполнения рассмотрим число $$k_i$$ камней-участников, проигравших не менее $$i$$ игр-сравнений. (Косвенные проигрыши - если $$a$$ проиграл $$b$$, а $$b$$ проиграл $$c$$, - не учитываются.) Легко понять, что сумма $$k_i$$ по всем $$i$$ равна числу игр, так как после каждой игры одно из $$k_i$$ увеличивается на единицу.

Поэтому достаточно показать, что каков бы ни был алгоритм, при неудачных для него результатах игр будет выполнено неравенство $$k_1+k_2 \ge n + \lceil log_2 n\rceil -2$$. Будем называть " лидерами " тех участников, которые еще никому не проиграли. В начале их $$n$$, а в конце остается только один лидер (поскольку любой из лидеров может быть победителем). Поэтому $$k_1 \ge n-1$$ (все игроки, кроме одного, кому-то проиграли). Объясним, как надо выбирать результаты матчей, чтобы добиться неравенства $$k_2\ge \lceil log_2n\rceil -2$$. Результат встречи двух не-лидеров может быть выбран любым. Если лидер встречается с не-лидером, то выигрывает лидер. При встрече двух лидеров выигрывает более опытный, то есть тот, кто выиграл к этому моменту больше игр (при равенстве - любой).

Чтобы доказать, что в этом случае выполнено искомое неравенство на $$k_2$$, введем отношения подчинения, считая при этом, что каждый игрок в любой момент игры подчинен ровно одному лидеру. В начале каждый сам себе лидер и подчинен только себе. При встрече лидера с не-лидером (или двух не-лидеров) подчинение не меняется; при встрече двух лидеров проигравший и все его подчиненные переподчиняются выигравшему.

Легко доказать по индукции, что если лидер выиграл $$k$$ игр, то группа его подчиненных (включая его самого) содержит не более $$2^k$$ человек. Вначале $$k=0$$ и в его группе только он сам. Если лидер выиграл $$k$$ игр и побеждает лидера, выигравшего не более $$k$$ игр, то в каждой из групп не более $$2^k$$ игроков, а в объединении не более $$2^{k+1}$$ игроков.

Следовательно, по окончании турнира лидер выиграл не менее $$\lceil log_2 n\rceil$$ игр, поскольку в его группе все $$n$$ игроков. Все побежденные им, кроме второго по силе игрока, проиграли еще кому-то (иначе почему мы уверены, что они не вторые по силе?). Отсюда и получается требуемая оценка на $$k_2$$.

4.5.7. Доказать, что оценка предыдущей задачи остается в силе, если требуется найти лишь второй по весу камень, а самый тяжелый искать не обязательно.

Указание. Если по окончанию турнира определился второй по силе игрок, то он кому-то проиграл (откуда мы знаем иначе, что он не первый?), и тем самым известен и победитель.

4.5.8. Дано $$n$$ различных по весу камней и число $$k$$ (от $$1$$ до $$n$$ ). Требуется найти $$k$$ -ый по весу камень, сделав не более $$Cn$$ взвешиваний, где $$C$$ - некоторая константа, не зависящая от $$k$$ и $$n$$.

Замечание. Сортировка позволяет сделать это за $$\text{Cn log n}$$ взвешиваний. Указание к этой (трудной) задаче приведено в лекции про рекурсию.

Следующая задача имеет неожиданно простое решение.

4.5.9. Имеется $$n$$ одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более $$n/2$$ ) одинаковых. Сделав не более $$n$$ взвешиваний, найти хотя бы один камень из этого большинства. (Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству.)

Указание. Если найдены два различных камня, то их оба можно выбросить - хотя бы один из них плохой и большинство останется большинством.

Решение. Программа просматривает камни по очереди, храня в переменной i число просмотренных камней. (Считаем камни пронумерованными от 1 до n.) Помимо этого программа хранит номер "текущего кандидата" c и его "кратность" k. Смысл этих названий объясняется инвариантом (И):

если к непросмотренным камням (с номерами i+1...n ) добавили бы k копий c -го камня, то наиболее частым среди них был бы такой же камень, что и для исходного массива.

Получаем такую программу:

k:=0; i:=0;
{(И)}
while i<>n do begin
| if k=0 then begin
| | k:=1; c:=i+1; i:=i+1;
| end else if (i+1-ый камень одинаков с c-ым) then begin
| | i:=i+1; k:=k+1;
| |  {заменяем материальный камень идеальным}
| end else begin
| | i:=i+1; k:=k-1;
| | {выкидываем один материальный и один идеальный камень}
| end;
end;
искомым является c-ый камень

Замечание. Поскольку во всех трех вариантах выбора стоит команда i:=i+1, ее можно вынести наружу.

Заметим также, что эта программа гарантирует отыскание наиболее частого камня, лишь если он составляет большинство.

Следующая задача не имеет на первый взгляд никакого отношения к сортировке.

4.5.10. Имеется квадратная таблица a[1..n,1..n]. Известно, что для некоторого i строка с номером i заполнена одними нулями, а столбец с номером i - одними единицами (за исключением их пересечения на диагонали, где стоит неизвестно что). Найти такое i (оно, очевидно, единственно). Число действий порядка n. (Заметим, что это существенно меньше числа элементов в таблице.)

Указание. Рассмотрите a[i][j] как результат "сравнения" i с j и вспомните, что самый тяжелый из n камней может быть найден за n сравнений. (Заметим, что таблица может не быть "транзитивной", но все равно при "сравнении" двух элементов один из них отпадает.)

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^