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(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] <= 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 <<q) and
      | | (x[p0+1] > r) and ((p0 = q) or ((p0= x[q0+1])))}
      | | b [s0+1] := x [q0+1];
      | | q0 := q0 + 1;
      | | s0 := s0 + 1;
      | end;
      end;

      (Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)

      Остается лишь переписать результат слияния обратно в x. (Предупреждение. Если обратное копирование выполняется вне процедуры слияния, то не забудьте переписать последний отрезок.)

      Программа имеет привычный дефект: обращение к несуществующим элементам массива при вычислении булевских выражений.

      Решение 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-поддерево назовем регулярным, если все его вершины регулярны. (В частности, любой лист образует регулярное одноэлементное поддерево.) Заметим, что истинность утверждения "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 имеет тип 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 довольно велика.

 

Другие записи

10.06.2016. 4.3. Применения сортировки
  4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка n*log n. (Эта задача уже была в главе о массивах.) Решение. Отсортировать числа, а затем посчитать…
10.06.2016. 4.4. Нижние оценки для числа сравнений при сортировке
  Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции…
10.06.2016. 4.5. Родственные сортировке задачи
  4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней? Решение. Очевидный алгоритм с инвариантом "найден самый легкий камень…