Глава 4. Сортировка.

        Глава 4. Сортировка.

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

     4.1.1. Пусть a[1],  ...,  a[n]  -  целые  числа.  Требуется
построить  массив  b[1],  ..., b[n], содержащий те же числа, для
которых b[1] <= ... <= b[n].
     Замечание. Среди чисел a[1]...a[n] могут быть равные.  Тре-
буется,  чтобы  каждое целое число входило в b[1]...b[n] столько
же раз, сколько и в a[1]...a[n].

     Решение. Удобно считать, что числа a[1]..a[n] и  b[1]..b[n]
представляют собой начальное и конечное значения массива x. Тре-
бование  "a  и b содержат одни и те же числа" будет заведомо вы-
полнено, если в процессе работы  мы  ограничимся  перестановками
элементов x.
  ...
  k := 0;
  {k наименьших элементов массива x установлены на свои места}
  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] <= ... <= x[k]}

     Решение.

  k:=1
  {первые k элементов упорядочены}
  while k <> n do begin
  | {k+1-ый элемент продвигается к началу, пока не займет
  |   надлежащего места }
  | t := k+1;
  | {x[1] <= ... <= x[t-1] и x[t-1], x[t] <= ... <= x[k+1] }
  | 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*n. Существуют более эффективные алгоритмы.

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

     4.2.1. Предложить алгоритм сортировки, число действий кото-
рого  было  бы  порядка  n  log  n,  то  есть не превосходило бы
C*n*log(n) для некоторого C и для всех n.

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

     Решение 1. (сортировка слиянием).
     Пусть  k  -  положительное  целое  число.  Разобьем  массив
x[1]..x[n]  на  отрезки  длины  k.  (Первый  - x[1]..x[k], затем
x[k+1]..x[2k] и т.д.) Последний отрезок будет неполным,  если  n
не  делится на k. Назовем массив k-упорядоченным, если каждый из
этих отрезков упорядочен. Любой массив 1-упорядочен. Если массив
k-упорядочен и n<=k, то он упорядочен.
     Мы  опишем,  как  преобразовать  k-упорядоченный  массив  в
2k-упорядоченный (из тех же элементов). С помощью этого преобра-
зования алгоритм записывается так:

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

     Требуемое  преобразование  состоит в том,что мы многократно
"сливаем" два упорядоченных отрезка длины не  больше  k  в  один
упорядоченный  отрезок. Пусть процедура слияние (p,q,r: integer)
при p <=q <= r сливает отрезки  x[p+1]..x[q]  и  x[q+1]..x[r]  в
упорядоченный  отрезок 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<q) and
  | |   (x[p0+1] >= 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. Та же задача, если ломаная должна быть замкнутой.

     Решение. Возьмем самую левую точку (т.е. точку с наименьшей
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 не убывали (сохраняя  притом  порядок  внутри
каждой из групп). Число действий порядка m+n.
     Указание. Завести m списков суммарной длины n (как это сде-
лать,  смотри в главе 6 о типах данных) и помещать в i-ый список
числа, для которых значение функции f равно i.  Вариант:  посчи-
тать  для  всех  i, сколько имеется чисел x c f(x)=i, после чего
легко определить, с какого места нужно начинать размещать  числа
с f(x)=i.

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

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

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

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

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

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

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

     Замечание.  Сортировка  позволяет  сделать это за C*n*log n
взвешиваний. Указание к этой (трудной) задаче приведено в  главе
про рекурсию.

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

     4.5.4. Имеется 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.5.  Имеется квадратная таблица a[1..n, 1..n]. Известно,
что для некоторого i строка с номером i заполнена одними нулями,
а столбец с номером i - одними единицами (за исключением их  пе-
ресечения на диагонали, где стоит неизвестно что). Найти такое i
(оно, очевидно, единственно). Число действий не превосходит C*n.
(Заметим, что это существенно меньше числа элементов в таблице).

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