Процедура переупорядочивания

Побуждением для следующего примера послужила работа Ч.А.Р. Хоара (Algoritm 64, C.A.C.M.).

Исходная задача - упорядочить значения элементов в заданном массиве A[1:N] и при заданном значении f (1 f N) так, чтобы после упорядочивания

при 1 k < f      A[k] A[f]

при f < k N      A[k] A[f]       (1)

В результате такого переупорядочивания A[f] равно f-му значению в порядке неубывания величин. Мы будем называть массив, удовлетворяющий (1), "расщепленным по f"; мы будем называть конечное значение A[f] "расщепляющим значением". Когда массив расщеплен, он разделен на две половины, одна половина - скажем, "левая" - содержит "маленькие" значения, а другая - скажем, "правая" - большие значения, а расщепляющее значение вставлено между ними. Общей функцией алгоритма является перемещение маленьких величин налево, а больших направо. Трудность состоит в том, что для данного f конечное значение A[f], то есть, критерия для "маленькое/большое" сначала неизвестно.

Изобретение Хоара состоит в следующем. Выберем произвольный критерий s для "маленькое/большое"; переместив маленькие элементы налево, а большие - направо, мы создадим некоторое расщепление по некоторой позиции. Если посчастливится, что s = f, то исходная задача решена. Ядром изобретения Хоара является то наблюдение, что в других случаях исходная задача может быть сведена к той же задаче, но теперь применяемой к одной из половинок, а именно, к левой половинке, если находится слева от расщепления и к правой половинке, если находится справа от расщепления.

Примечание. Альтернативным подходом будет полная сортировка массива: после нее A[f] будет равно f-му значению в порядке неубывания величин. Но это обойдется дороже, для этого случая мы должны установить отношения (1) для всех значений f. Фактически, мы достигаем того, что процедура переупорядочивания сама может использоваться для полной сортировки; учитывая этот факт, когда создано расщепление по s, A[s] содержит значение, которое оно должно содержать в полностью отсортированном массиве, и что - поскольку все элементы слева от него A[s], а элементы справа от него A[s] - полная сортировка может теперь быть выполнена на правой и левой частях независимо.

Теперь мы сосредоточим наше внимание на процедуре переупорядочивания для случая расщепления секции массива

      A[m] ... A[n]       при 1 m n N .

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

Мы собираемся выбрать одно из значений в массиве как "расщепляющее значение"; когда мы выберем это значение, его конечная позиция, т.е., позиция расщепления, будет неизвестна в начале работы алгоритма; она определится, когда алгоритм будет выполнен, другими словами, она определяется выполнением вычислений. Это предполагает, что мы строим коллекцию маленьких значений, начиная с левого конца, и коллекцию больших значений, начиная с правого конца, и продолжаем делать это, пока две коллекции не встретятся где-то посередине. Чтобы быть более точным, мы вводим два указателя, скажем, "i" и "j", конечными значениями которых будут "m" и "n" соответственно, и переупорядочиваем значения таким образом, что, если мы назовем расщепляющее значение V, то у нас обеспечивается, что

      A[k] V при m k < i и
      A[k] V при j k < n .

При выбранном расщепляющем значении алгоритм должен строить коллекции маленьких и больших значений соответственно где-то снаружи. Алгоритм может начать просмотр, скажем, с левого края, пока не встретится большой элемент. Когда это произойдет, значение должно быть перемещено из коллекции маленьких значений, т.е., оно должно быть добавлено в коллекцию больших элементов. Фактически, это первый элемент, "большесть" которого установил алгоритм: поскольку мы решили строить коллекции снаружи, это большое значение должно быть присвоено A[n]. Поскольку мы хотим, чтобы эта позиция в массиве была "свободной" - т.е., способной принять это первое большое значение - исходной значение A[n] может быть убрано из массива в начале и может быть выбрано как расщепляющее значение V.

То есть, мы инициализируем i = m и j = n и "убираем" A[n] - присваиванием его переменной V, - таким образом инициализируя ситуацию, в которой просмотр начинается с элемента A[i], тогда как j указывает на только что сделанную "дырку". Когда просмотр вверх (под управлением увеличивающегося "i") находит большой элемент, т.е., когда в первый раз A[i] > V, это значение помещается в дырку, теперь дырка остается на том месте, куда указывает "i". С этого момента может работать просмотр вниз (под управлением уменьшающегося "j"), пока не встретится маленький элемент, который будет помещен в дырку в позиции i, оставляя дырку в позиции, на которую указывает j. Такие просмотры вверх и вниз должны следовать друг за другом, пока не выполнится условие i = j, т.е., пока оба не будут указывать на дырку в позиции, по которой будет выполнено расщепление. Наконец, дырка принимает значение V, которое было выбрано в начале.

Вышеприведенный эскиз дает неформальное описание существенных свойств алгоритма, никоим образом не устанавливая структуру последовательной программы, которая его воплотит.

Я попытался сделать программу, в которой ядро состоит из программной части для восходящего просмотра и программной части для нисходящего просмотра. Первая часть содержит цикл с в повторяющемся операторе. Две части вместе формируют повторяющийся оператор внешнего цикла. Эта программа получилась очень некрасивой и запутанной, причиной этому было то, что завершение могло произойти потому, что либо восходящий просмотр, либо нисходящий доходил до дырки. Рассуждения, необходимые для установления того, что программа правильно завершится становились мучительными.

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

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

up = true означает:	алгоритм находится в стадии восходящего просмотра и j указывает на дырку
up = false означает:	алгоритм находится в стадии нисходящего просмотра и i указывает на дырку

Инициализация должна быть расширена присваиванием "up:= false"; после инициализации программа продолжается:

      "while i < j do выполнить соответствующий шаг"

В процессе выполнения действия "выполнить соответствующий шаг" значение "" должно измениться, когда дырка заполняется и направление просмотра изменяется на противоположное. Без дополнительных разговоров я ввожк следующую процедуру:

    integer procedure split(real array a, integer value m, n);
    begin integer i, j; real V; boolean up;
          i:= m; j:= n; V:= a[i]; up:= true;
          while i < j do
          begin if up then
                   if a[i] > V do begin a[j]:= a[i]; up:= false end
                      else
                   if V > a[i] do begin a[i]:= a[j]; up:= true end
                if up then i:= i + 1 else j:= j + 1;
          end;
          a[j]:= V; split:= j;
    end

При ее применении мы должны только вызвать процедуру "split" для m < n; она поддерживается также и для случая m = n.

Упражнение. Покажите, что в версии расщепления, которая поддерживает только случай для m < n, его внутренний цикл может управляться также выражением repeat until.

Примечание. Ценой большего количества операций индексации текст процедуры может быть сокращен тем, что не вводится отдельная переменная V, а это значение сохраняется "в дырке", т.е.

    V = if up then a[j] else a[i]

В результате расщепляющее значение зигзагами перемещается на свою конечную позицию. При вышеприведенных соглашениях обе проверки "a[i] > V" и "V > a[i]" превращаются в "a[i] > a[j]", оба присваивания "a[j]:= a[i]" и "a[i]:= a[]j]" превращаются в обмен

    W:= a[i]; a[i]:= a[j]; a[j]:= W

а оба присваивания "up:= false" и " up:= true" могут быть представлены

    up:= non up

Вышеприведенные соображения позволяют нам сократить текст процедуры до

    integer procedure split(real array a, integer value m, n);
    begin integer i, j; real W; boolean up;
          i:= m; j:= n; up:= true;
          while i < j do 
          begin if a[i] > a[j] do
                begin W:= a[i]; a[i]:= a[j]; a[j]:= W; up:= non up end;
                if up then i:= i + 1 else j:= j -1;
          end;
          split:= j
    end

(Конец примечания)

Теперь мы вернемся к исходной задаче: дан массив A[1:N] и значение f (1 f N), переупорядочить элементы так, чтобы

при 1 k < f      A[k] A[f]

при f < k N      A[k] A[f]       ;

в результате чего A[f] будет равен f-му элементу в порядке невозрастания величин.

Идея состоит в применении оператора "split" сначала к исходному массиву от 1 до N. Оператор установит расщепление по какой-то позиции, скажем, s. Если позиция расщепления совпадает с f (f = s), мы достигли своей цели, иначе оператор "split" применяется к одной из половинок, а именно, к левой половине, если f < s и к правой половине, если f > s.

Для этих целей мы водим переменные p и q, удовлетворяющие

    1  p  f  q  N

так, что

    A[p] ... A[q]

будет секцией массива, для которой будет применяться расщепление, так как эта секция определенно содержит (будущее) значение A[f].

Если расщепление находится справа от f (т.е., f < s), оператор должен быть применен к левой половине, т.е., q должно быть переустановлено в s - 1, а p остается неизменным; в случае же f > s, p должно быть переустановлено в s + 1, а q остается неизменным. Мы приходим к процедуре

    integer p, q, s;
    p:= 1; q:= N;
    repeat s:= split(A, p, q);
           if f < s do q:= s - 1;
           if f > s do p:= s + 1;
    until f = s

(Примечание. Эта программа может вызывать процедуру "split" с m = n.)

Мы можем захотеть усовершенствовать эту программу: скорее всего, вызов "split" с p = q избыточен: если секция состоит из единственного элемента, никакого переупорядочивания произойти не может: расщепление пройдет по этому единственному элементу, обе половинки будут пустыми. Отношение p < q дает нам другой необходимый критерий продолжения, и мы можем посмотреть, не сделать ли его единственным критерием продолжения. Поскольку мы хотим привязаться к p f q, завершение через удачное попадание в f, т.е., f = s должно порождать p = f = q. Следующая программа будет достигать этого результата.

    integer p, q, s;
    p:= 1; q:= N;
    while p < q do
    begin s:= split(A, p, q);
          if f = s then begin p:= f; q:= f end
                   else if f < s then q:= s - 1 else p:= s + 1
    end

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

Более сложное использование оператора "split" состоит в полной сортировке массива, заметим, что после применения оператора "split", как минимум, один элемент (а именно, ) достигает своей конечной позиции, тогда как другие элементы, хоть и не обязательно становятся в свои конечные позиции, но будут находиться в правильной половинке секции, так что сортировка будет состоять в раздельных сортировках обеих половинок.

Несколько наивным подходом является рекурсия

    procedure sort(real array a, integer value p, q);
    begin integer s;
          s:= split(a, p, q);
          if p < s - 1 do sort(a, p, s - 1);
          if s + 1 < q do sort(a, s + 1, q)
    end

    sort(A, 1, N)

будет сортировать весь массив. Опять-таки используется то, что сортировка секции массива является необходимой операцией только, если секция содержит, как минимум, два элемента. (Процедура "sort" может вызываться для секции с только одним элементом, но такие вызовы не будут генерироваться.)

Мы назвали приведенную процедуру наивной, и мы сделали это по следующим причинам. Оператор "split" может делить предлагаемую ему секцию на две очень неравные части (т.е., когда исходный крайний справа элемент имеет значение, близкое к максимальному); в результате максимальная динамическая глубина рекурсивных вызовов может расти пропорционально N, длине секции массива. Поскольку рекурсивные вызовы требует объема памяти, пропорционального динамической глубине, данная программа может стать слишком затратной по требованиям к памяти. Это приводит к заключению о том, что рекурсивная сортировка непрактична, фактически что легкое переупорядочивание в процедуре "sort" гарантирует, что максимальная динамическая глубина не будет превышать log2 N. Имея в виду существование такой процедуры сортировки, мы назвали предыдущую программу "наивной".

Мы можем гарантировать, что процедура сортировки не будет порождать динамическую глубину более log2 N, если при вызове "split" она будет предписывать рекурсивный вызов самой себя только для сортировки меньшей из двух половинок. (В случае, когда две половинки имеют одинаковую длину, выбор не имеет значения.) Применение "sort" рекурсивно только к меньшей половинке приводит к тому, что другая половинка не отсортирована, но это может быть повторным применением этой половинной сортировки к еще не отсортированной секции. В теле "sort" введены две переменные "pu" и "qu", указывающие на левый и правый концы еще не отсортированной секции.

    procedure sort(real array a, integer value p, q);
    begin integer s, pu, qu;
          pu:= p; qu:= q;
          while pu < qu do
          begin s:= split(a, pu, qu);
                if qu - s < s - pu then
                   begin if s + 1 < qu do sort(a, s + 1, qu); qu:= s - 1 end
                                  else
                   begin if pu < s - 1 do sort(a, pu, s - 1); pu:= s + 1 end
          end
    end

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

Примечание. Если с самого начала элементы массива A упорядочены по неуменьшению, то чрезмерной глубины рекурсивных вызовов не будет, но алгоритм останется затратным по времени (пропорционально N2). Это дает повод для усовершенствования процедуры "": вместо того, чтобы брать вслепую крайний правый элемент секции массива в качестве расщепляющего значения, в начало "split" может быть вставлен некоторого рода небольшой поиск возможно лучшего приближения к серединному значению; этот элемент может быть обменен с крайним правым элементом, и после этого расщепление продолжается так, как это было описано.

Упражнение. Докажите, что выход из цикла будет гарантированно иметь место при pu = qu. (Это не так очевидно, как вы можете подумать!)