Таблица 1

обменная сортировка со слиянием (метод бэтчера)

р q г d

503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

8 8 0 8

503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703

4 8 0 4

503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703

4 4 4 4

503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703

2 8 0 2

154 061 503 087 512 170 612 275 653 426 765 оОЭ 897 677 908 703

2 4 2 6

154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703

154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703

1801

061 154 087 503 170 512 275 612 426 653 509 765 677 897 703 908

14 17

061 154 087 503 170 512 275 612 426 653 509 765 677 897 703 908 12 13 V >CJ><L ><1 J><C ><C

061 154 087 275 170 426 503 509 512 653 612 703 677 897 765 908

1111 W W W W W W W

061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

"перегиб" относительно диагонали при необходимости, чтобы путь нигде не проходил выше диагонали (рис. 18, (Ь) и доказательство в упр. 10). На следуюш,ей итерации шага МЗ имеем р = г - liid = 2" - 1,2~ - 1,..., 1. В результате произойдет сравнение и/или обмен записей i?2:T?2+d, Ri:Ri+d и т. д. Опять же, имеется простая геометрическая интерпретация: путь "перегибается" относительно прямой, расположенной на {d + 1) единиц ниже диагонали (рис. 18, (с) и (d)). В конце концов, получаем путь, изображенный на рис. 18, (е), который соответствует полностью рассортированной перестановке. На этом "геометрическое доказательство" справедливости алгоритма Бэтчера завершается (данный алгоритм можно было бы назвать сортировкой посредством перегибов!).

МХХ-программа для алгоритма М приведена в упр. 12. К сожалению, количество вспомогательных операций, необходимых для управления последовательностью сравнений, весьма велико, так что программа менее эффективна, чем другие рассмотренные выше методы. Однако она обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией шага МЗ, можно выполнять одновременно на компьютерах или в сетях, которые реализуют параллельные вычисления. С такими параллельными операциями сортировка осу-

Рис. 18. Геометрическая интерпретация метода Бэтчера, N = 16.

ществляется за fig-1 (fg-l + l) шагов, и это один из самых быстрых общих методов среди всех известных. Например, 1 024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Его ближайшим соперником является метод Пратта (см. упр. 5.2.1-30), который затрачивает 40 или 73 шага в зависимости от того, как считать: если допускать перекрытие сравнений до тех пор, пока не потребуется выполнять перекрывающиеся обмены, то для сортировки 1 024 элементов методом Пратта требуется всего 40 циклов сравнения и/или обмена. Дальнейшие пояснения приводятся в разделе 5.3.4.

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

Основная идея, на которой базируется этот метод, состоит в том, чтобы взять одну из записей, скажем Ri, и передвинуть ее на то место, которое она должна занять после сортировки, скажем в позицию s. В поиске этой окончательной позиции придется несколько перекомпоновать и остальные записи таким образом, чтобы слева от позиции s не оказалось ни одной записи с большим ключом, а справа - с меньшим. В результате последовательность окажется разбитой таким образом, что исходная задача сортировки всего массива записей будет сведена к задачам независимой сортировки пары подмассивов Ri...Rs-i и Rs+i...Rn меньшей длины. Далее, тот же метод применяется и к полученным подмассивам до тех пор, пока не будет завершена сортировка всей последовательности. Существует несколько способов разбиения всей последовательности на подмассивы. Рассмотрим следующую процедуру, предложенную Седгевиком, которая, на наш взгляд, является лучшей из имеющихся на сегодняшний день, в основном, вследствие своей "прозрачности" и простоты анализа алгоритма. Итак, пусть имеются указатели г и j, причем вначале i = 2 и j = N. Предположив, что запись Ri должна после разделения принадлежать левому подмассиву (это легко определить, сравнив Ki с Ki), увеличим i на 1 и продолжим далее до тех пор, пока не обнаружим такую запись Ri, которая

принадлежит правому подмассиву. Аналогично будем уменьшать j на 1 до тех пор, пока не обнаружим такую запись Rj, которая принадлежит левому подмассиву. Если г < j, поменяем местами Ri с Rj; затем повторим аналогичную процедуру со следующей записью, "сжигая свечку с обоих концов", пока не станет i > j-Завершается процесс разделения массива обменом записей Rj с Ri. Посмотрим, например, что произойдет с нашей последовательностью из шестнадцати чисел.

Исходный массив: [503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703]

1-й обмен: 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

2-й обмен: 503 087 154 061 908 170 897 275 653 426 512 509 612 677 765 703

3-й обмен: 503 087 154 061 426 170 897 275 653 908 512 509 612 677 765 703

Переключение указателей: 503 087 154 061 426 170 275 897 653 908 512 509 612 677 765 703

Разделенный массив: [275 087 154 061 426 170]503[897 653 908 512 509 612 677 765 703]

t t j i

(Для удобства анализа положения i и j ключи Ki и Kj выделены в таблице полужирным шрифтом.)

В табл. 2 показано, как выбранная нами для примеров последовательность полностью сортируется при помощи этого метода за И итераций. В скобки заключены подмассивы, которые еще предстоит рассортировать; в программе эти подмассивы можно представлять двумя переменными двоичными {1,г) (границы рассматриваемого в данный момент массива) и стеком дополнительных пар {1к,Гк)- Каждый раз, когда массив разбивается, помещаем в стек больший из подмассивов и начинаем обрабатывать оставшийся; и так до тех пор, пока не будут получены тривиально короткие массивы. Как показано в упр. 20, такая процедура гарантирует, что в стеке никогда не будет находиться более Ig N элементов.

Только что описанную процедуру сортировки можно назвать обменной сортировкой с разделением. Ее идея принадлежит Ч. Э. Р. Хоару, интереснейшая статья которого [С. А. R. Ноаге, Сотр. J. 5 (1962), 10-15] - одно из наиболее исчерпывающих из когда-либо опубликованных сообщений об этом методе. Хоар окрестил свой метод "quicksort" ("быстрая сортировка"), и это название вполне соответствует действительности, так как внутренний цикл вычислений при реализации на любом из современных компьютеров оказывается очень быстрым. При всех сравнениях, выполняемых на текущей итерации, используется один и тот же ключ, так что соответствующее значение можно держать в регистре. Обмен тактами между сравнениями выполняется только в отношении единственного индекса. Более того, количество перезаписей данных довольно мало - обработка табл. 2, например, требует всего лишь 17 операций перезаписи данных.

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