Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.

Ни один из элементов a[i],..., a[i-l] не превышает a[i].

Ни один из элементов a[i+l],.--, а[г] не является меньшим a[i].

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

Программа 7.1. Быстрая сортировка

Если в массиве имеется один или меньшее число элементов, то ничего делать не надо. В противном случае массив подвергается обработке со стороны процедуры partition (см. программу 7.2), которая помещает элемент а[1] для некоторого i в позицию между I и г включительно и переупорядочивает остальные элементы таким образом, что рекурсивные вызовы этой процедуры должным образом завершают сортировку.

template <class Item>

void quicksort (Item a[], int 1, int r)

if (r <= 1) return; int i = partition(a, 1, r) ; quicksort(ar 1, i-1); quicksort(a, i+1, r) ;

asort i ngexample

a a E(Dt I ngoxsmplr a a(D a®

lingopm(r)xts

L I G(M)0 P N

(G)i U

(n)p о ®p ®

(s)t x t®

aaeegi lmnoprstx

РИСУНОК 7.1. ПРИМЕР БЫСТРОЙ СОРТИРОВКИ

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

Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента {partitioning element) произвольно выбирается элемент а[г] - он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Мы продолжаем дальше в том же духе, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента, как показано на следующей диаграмме

Здесь V есть ссылка на разделяющий элемент, i - на левый указатель, а j - на правый указатель. Как показано на диаграмме, целесообразно останавливать просмотр слева на элементах, больших или равных разделяющему, а просмотр справа - на элементах, меньших или равных элементу разделения, даже если подобная стратегия может привести к лишним обменам элементов, равных по значению разделяющему (далее в этом разделе упоминаются аргументы, говорящие в пользу такой стратегии). Когда указатели просмотра пересекаются, все, что необходимо сделать в этом случае - это обменять элемент а [г] с крайним левым элементом правого подфайла (на этот элемент указывает левый указатель). Программа 7.2 содержит реализацию этого процесса, а на рис.7.2 и 7.3 приводятся примеры.

Внутренний цикл быстрой сортировки увеличивает значение указателя на единицу и сравнивает элементы массива с конкретным фиксированным значением. Именно эта простота и делает быструю сортировку быстрой: трудно себе представить более короткий внутренний цикл в алгоритме сортировки.

Программа 7.2 использует явную проверку, чтобы прекратить просмотр, когда разделяющий элемент является наименьшим элементом массива. Возможно, во избежание подобной проверки стоило бы воспользоваться служебным значением: внутренний цикл быстрой сортировки настолько мал, что одна лишн5ш проверка может оказать заметное влияние на эффективность алгоритма. Служебное значение не требуется в данной реализации, когда разделяющим элементом оказывается наибольший элемент файла, поскольку сам разделяющий элемент находится на правом конце массива, что является условием завершения просмотра. Другие реализации разделения, которые рассматриваются далее в разделе и в ряде мест главы, не обязательно останавливают просмотр, если проверяемый ключ равен разделяю-

ASORT I NGEXAMPL(D AS

А М Р L

А А S М Р L Е

А А Е

О X S М Р L Е

Е R Т I N G А А E(Dt I NGOXSMPLR

РИСУНОК 7.2. РАЗДЕЛЕНИЕ В БЫСТРОЙ СОРТИРОВКЕ

Разделение в быстрой сортировке начинается с выбора (произвольного) разделяющего элемента. В программе 7.2 для этой цели используется самый правый элемент Е. Затем выполняется просмотр слева с пропуском элементов с меньшими значениями и справа с пропуском элементов с большими значениями, обмен элементов, на которых просмотры остановились, после чего просмотр продолжается до тех пор, пока значения указателей не совпадут. Мы начинаем с просмотра слева и останавливаемся на S, затем проводится просмотр справа, который останавливается на элементе А, после чего производится обмен местами элементов SuA. Далее процесс продолжается слева до тех пор, пока не остановится на О, после чего продолжается просмотр справа до тех пор, пока он не остановится на элементе Е, и обмен Ои Е. После этого указатели просмотра пересекаются: мы продолжаем просмотр слева, пока не остановимся на r, продолжаем просмотр справа (минуя r), пока не остановимся на Е. Рассматриваемый процесс завершается тем, что разделяющий элемент (правый Е) обменивается с r.

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

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

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

Когда в файле встречаются дубликаты ключей, фиксация момента пересечения указателей сопряжена с определенными трудностями. Процесс разбиения можно слегка усовершенствовать, если остановить просмотр при i<j, а затем воспользоваться значением j, а не чтобы определить правую границу левого подфайла при первом рекурсивном вызове. В таком случае выполнение еще одной итерации цикла следует рассматривать как усовершенствование, поскольку оба цикла просмотра прекращаются, когда j и i ссылаются на один тот же элемент, в результате два элемента занимают свои окончательные позиции; один из них - это элемент, который остановил оба просмотра и в силу этого обстоятельства должен быть равен разделяющему элементу, а также и сам разделяющий элемент. Подобная ситуация могла бы возникнуть, например, если бы на рис. 7.2 R был Е. Это изменение, по-видимому, заслуживает того, чтобы его внести в программу, ибо в данном конкретном случае программа в том виде, в каком она здесь представлена, оставляет запись с ключом, равным ключу разделяющего элемента, в а[г], и это приводит к тому, что первое разделение, выполняемое за счет вызова quicksort(a, i+1, г), вырождается, поскольку самый правый ключ оказывается наименьшим. Однако, реализацию разделения, используемую в программе 7.2, несколько проще понять, так что в дальнейшем мы будем ссылаться на нее как на базовый метод разделения, применяемый в быстрой сортировке. Если в сортируемом файле присутствует значительное число дублированных ключей, то на передний план выступают другие факторы. Они будут рассматриваться несколько позже.