Если в массиве имеется один или меньшее число элементов, то ничего делать не надо. В противном случае массив подвергается обработке со стороны процедуры partition (см. программу 15), которая помещает элемент a[i] для некоторого i в позицию между I и r включительно и переупорядочивает остальные элементы таким образом, что рекурсивные вызовы этой процедуры должным образом завершают сортировку.
template <class Item>
void quicksort(Item a[], int 1, int r)
{
if (r <= 1) return;
int i = partition (a, 1, r);
quicksort(a, 1, i-1);
quicksort(a, i+1, r);
}
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента {partitioning element) произвольно выбирается элемент а[r] — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Мы продолжаем дальше в том же духе, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента, как показано на следующей диаграмме
Здесь v есть ссылка на разделяющий элемент, i — на левый указатель, a j — на правый указатель. Как показано на диаграмме, целесообразно останавливать просмотр слева на элементах, больших или равных разделяющему, а просмотр справа — на элементах, меньших или равных элементу разделения, даже если подобная стратегия может привести к лишним обменам элементов,
|
|
равных по значению, разделяющему (далее в этом разделе упоминаются аргументы, говорящие в пользу такой стратегии). Когда указатели просмотра пересекаются, все, что необходимо сделать в этом случае — это обменять элемент, а [r] с крайним левым элементом правого подфайла (на этот элемент указывает левый указатель). Программа 15 содержит реализацию этого процесса, а на рис.28 и 29 приводятся примеры.
Внутренний цикл быстрой сортировки увеличивает значение указателя на единицу и сравнивает элементы массива с конкретным фиксированным значением. Именно эта простота и делает быструю сортировку быстрой: трудно себе представить более короткий внутренний цикл в алгоритме сортировки.
Программа 15 использует явную проверку, чтобы прекратить просмотр, когда разделяющий элемент является наименьшим элементом массива. Возможно, во избежание подобной проверки
стоило бы воспользоваться служебным значением: внутренний цикл быстрой сортировки настолько мал, что одна лишняя проверка может оказать заметное влияние на эффективность алгоритма. Служебное значение не требуется в данной реализации, когда разделяющим элементом оказывается наибольший элемент файла, поскольку сам разделяющий элемент находится на правом конце массива, что является условием завершения просмотра. Другие реализации разделения, которые рассматриваются далее в разделе и в ряде мест главы, не обязательно останавливают просмотр, если проверяемый ключ равен разделяющему элементу — возможно, в таких реализациях и потребуется еще одна проверка во избежание ситуации, когда указатель смещается с правого конца массива. С другой стороны, усовершенствование быстрой сортировки, имеет своим положительным побочным эффектом то обстоятельство, что
|
|
отпадает необходимость как в проверке, так и в наличии самого служебного значения на каждом конце.
Процесс разделения неустойчив, поскольку во время любой операции обмена любой ключ может пройти мимо большого числа равных ему ключей (которые остаются непроверенными). Простые способы сделать быструю сортировку, ориентированную на массивы, устойчивой, пока не известны.
Реализацию разделяющей процедуры следует выполнять с особой осторожностью. В частности, наиболее простой способ гарантировать завершение рекурсивной программы заключается в том, что (i) она не вызывает себя для файлов с размерами 1 и менее и (ii) вызывает себя только для файлов, размер которых строго меньше размеров входного файла. Эти стратегии на первый взгляд кажутся очевидными, однако при этом легко упустить из виду такие свойства ввода, которые в конечном счете могут послужить причиной неудачи. Например, обычная ошибка в реализации быстрой сортировки заключается в отсутствии гарантии того, что каждый элемент всегда будет поставлен в нужное место, а также в возможности вхождения программы сортировки в бесконечный цикл в случаях, когда разделяющим элементом служит наибольший или наименьший элемент файла.
|
|
Когда в файле встречаются дубликаты ключей, фиксация момента пересечения указателей сопряжена с определенными трудностями. Процесс разбиения можно слегка усовершенствовать, если остановить просмотр при i<j, а затем воспользоваться значением j, а не i-1, чтобы определить правую границу левого подфайла при первом рекурсивном вызове. В таком случае выполнение еще одной итерации цикла следует рассматривать как усовершенствование, поскольку оба цикла просмотра прекращаются, когда j и i ссылаются на один тот же элемент, в результате два элемента занимают свои окончательные позиции: один из них — это элемент, который остановил оба просмотра и в силу этого обстоятельства должен быть равен разделяющему элементу, а также и сам разделяющий элемент. Подобная ситуация могла бы воз- возникнуть, например, если бы на рис. 28 R был Е. Это изменение, по-видимому, заслуживает того, чтобы его внести в программу, ибо в данном конкретном случае программа в том виде, в каком она здесь представлена, оставляет запись с ключом, равным ключу разделяющего элемента, в а[r], и это приводит к тому, что первое разделение, выполняемое за счет вызова quicksort (a, i+1, r), вырождается, поскольку самый правый ключ оказывается наименьшим. Однако, реализацию разделения, используемую в программе 15, несколько проще понять, так что в дальнейшем мы будем ссылаться на нее как на базовый метод разделения, применяемый в быстрой сортировке. Если в сортируемом файле присутствует значительное число дублированных ключей, то на передний план выступают другие факторы.
Рис.28. Разделение в быстрой сортировке