Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 31
Текст из файла (страница 31)
М2. (Начальная установка е, г, и',) Установить и +- 2" ', г <- О, и' е- р. МЗ. (Цикл по 1.) Для всех 1, таких, что О < 1 < Х вЂ” и' н 1Л р = г, вьшолнить шаг М4. Затем перейти к шагу М5, (Здесь через ( А р обозначена операция "~юрвзрядное логическое Иь над предо швлениями целых чисел 1 и р; все биты результата равны О, кроме тех битов, для которых в соответствующих разрядах 1 и р находятся 1. Так, 13 Л 21 = (1101)э Л (10101)э — — (00101)э = 5.
К этому моменту и — нечетное кратное р (т. е. частное от деления д на р нечетно), а р — степень двойки, так что (Лр„.Е (1+ 0) Л р. Отсюда следует, что шаг М4 можно выполнить при всех нужных значениях ( в любом порядке или даже одновременно.) М4. (Сравнение/обмен В;+,.В;+э ~,] Если К;+~ > К~~~+ы поменять местами записи Вьы е+ В,+„+,. 345. (Цикл по 9.! Если в Ф р, установить и' ~- в — р, и е- в/2„г +- р и возвратиться к шагу МЗ. Мб [11икл по р.] (К этому моменту перестановка К~ Кз... Км будет р-упорядочена.) Установить р+- (р/2). Если р > О, возвратиться к шагу М2.
$ В табл. 1 этот метод проиллюстрирован при Ю = 16. Обратите внимание на то, что, по существу, алгоритм сортирует Х элементов путем независимой сортировки подмассивов Вы Вз, Вы... и Вэ, Вэ, Вэ,..., после чего выполняются шаги М2-М5 при р = 1 для слияния двух рассортированных последовательностей. Чтобы доказать, что магическая последовательность сравнений и/или обменов, описанная в алгоритме М, действительно позволяет рассортировать любую последовательность В~ Вэ... Вл, несбходимо показать только, что в результате выполнения шагов М2-М5 при р = 1 будет слита любая 2-упорядоченная последовательность В~ Вз...
Вм. С этой целью можно воспользоваться методом решеточных диаграмм из раздела 5.2.1 (см. рис. 11 на с. 106); каждая 2-упорядоченная перестановка множества (1, 2,..., Аг) соответствует на решетке единственному пути из вершины (0,0) к (ГЛА/2), (Х/2)). На рис, 18, (а) показан пример прн В = 16, соответствующий перестановке 13241051161371481591612. При р = 1, д = 2' ~, г = О, д = 1 на шаге МЗ выполняется сравнение (и, возможно, обмен) записей В~.Вю Вз'В4 и т.
д, Этой операции соответствует простое преобразование пути на решетке: Таблица 1 ОБМЕННАЯ СОРТИРОВКА СО СЛИЯНИЕМ (МЕТОД БЭТэ!ЕРА) 503 087 512 061 903 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 бэЗ 426 512 509 908 677 897 703 503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703 г 1 0 2 '~ЬС / 154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703 2 4 2 б 154 061 503 087 512 170 612 275 653 426 765 э09 897 677 908 703 154 061 503 087 512 170 612 275 бэЗ 426 765 509 897 677 908 703 061 154 087 э03 170 512 275 612 426 653 э09 76э 677 897 703 908 1801 1417 061 И4 087 503 170 512 275 612 426 653 509 765 677 897 703 908 1213 061 154 087 275 170 426 503 509 512 653 612 703 677 897 765 908 061 087 И4 170 275 426 503 509 512 612 653 677 703 765 897 908 "перегиб" относительно диагонали при не1бходимости, чтобы путь нигде не прс ходил выше диагонали (рис.
18, (Ь) и доиаательство в упр. 10). На следующей итерации шага МЗ имеем р = г = 1 н Ы = '2' ' — 1,2' з — 1,...,1. В результате произойдет сравнение и/или обмен записей Вз:Лз+ю В4:Ь4+л и т. д. Опять же, имеется простая геометрическая интерпретация: путь "перегибается" относительно прямой, расположенной на з1(4(+ 1) единиц ниже диагонали (рис.
18, (с) и (6)). В конце концов, получаем путь, изображенный на рис. 18, (е), который соответствует полностью рассортированной перестановке. На зтом "геометрическое доказательство" справедливости алгоритма Бзтчера завершается (данный алгоритм можно было бы назвать сортировкой посредством перегибов!). ИХХ-программа для алгоритма М приведена в упр. 12. К сожалению, количество вспомогательных операций, необходимых для управления последовательностью сравнений, весьма велико, так что программа менее эффективна, чем другие рассмотренные выше методы.
Однако она обладает одним важным компенсирующим качеством: все сравнения н/или обмены, определяемые данной итерацией шага МЗ, можно выполнять одновременно на компьютерах нлн в сетях, которые реализуют параллельные вычисления. С такими параллельными операциямн сортировка осу- Рис. 18. Геометрическая интерпретация метода Бэтчера, Х = 1б. ществляется за -'(15Х)()'15Ф) + 1) шагов, н это один из самых быстрых общих методов среди всех известных.
Например, 1 024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных пшгов. Его ближайшим соперником является метод Пратта (см. упр. 5.2.1-30), который затрачивает 40 или 73 шага в зависимости от того, как считать: если допускать перекрытие сравнений до тех пор, пока не потребуется выполнять перекрывающиеся обмены, то для сортировки 1 024 элементов методом Пратта требуется всего 40 циклов сравнения и~или обмена. Дальнейшие пояснения приводятся в разделе 5.3.4.
Быстрая сортировка. В методе Бзтчера последовательность сравнений предопределена: каждый раз сравниваются одни и те же пары ключей независимо от информации о сортируемой последовательности, которую могут предоставить уже выполненные операции сравнения. Это утверждение в большой мере справедливо и применительно к методу пузырька, хотя алгоритм В использует в ограниченной степени полученные сведения, чтобы сократить объем работы в крайней справа части последовательности.
Обратимся теперь к озвсем иной стратегии, при которой для определения, какие ключи сравнивать следующими, используется результат каждого сравнения. Такая стратегия не годится для параллельных вычислений, но она может оказаться плодотворной для обычных компьютеров с последовательным выполнением операций. Основная идея., на которой базируетси этот метод, состоит в том, чтобы взять одну из записей, скажем Лы и передвинуть ее на то место, которое она должна занять после сортировки, скажем в позицию э.
В поиске этой окончательной позиции придется несколько перекомпоновать н остальные записи таким образом, чтобы слева от позиции э не оказалось ни одной записи с ббльшим ключом, а справа — с меньшим. В результате последовательность окажется разбитой таким образом, что исходная задача сортировки всего массива записей будет сведена к задачам независимой сортировки пары подмассивов Ям .. Я, 1 н В,+1... Лп меньшей длины.
Далю, тот же метод применяется и к полученным подмвссивам до тех пор, пока не будет завершена сортировка всей последовательности. Существует несколько способов разбиения всей последовательности на подмассивы. Рассмотрим следующую процедуру, предложенную Седгевиком, которая, на наш взгляд, является лучшей из имеющихся на сегодняшний день, в основном, вследствие своей "прозрачности" и простоты анализа алгоритма. Итак, пусть имеются указатели 1 и,у, причем вначале 1 = 2 и,~ = Ж.
Предположив, что запись 11; должна после разделения принадлежать левому подмасснву (зто легко определить, сравнив К, с К1), увеличим 1 на 1 и продолжим далее до тех пор, пока не обнаружим такую запись Ви которая принадлежит правому подмассиву. Аналогично будем уменьшать 7' на 1 до тех пор, пока не обнаружим такую запись Ну, которая принадлежит левому подмассиву. Если 1 < 1, поменяем местами Я; с Н", затем повторим аналогичную процедуру со следующей записью, "сжигая свечку с обоих концов", пока не станет 1 > 7', Завершается процесс разделения массива обменом записей ЛЗ с Нм Посмотрим, например, что произойдет с нашей последовательностью из шестнадцати чисел.
Исходный массив; [503 087 1-й обмен: оОЗ 087 2-й обмен: 503 087 3-й обмен: 503 087 Переключение указателей: 503 087 Разделенный массив: [275 087 Ы 2 061 908 170 897 275 653 426 154 509 612 677 765 703] $12 061 908 170 897 275 653 426 1$4 509 612 677 765 703 154 061 908 170 897 275 653 426 512 509 612 677 765 703 154 061 426 170 897 27Ь 653 908 Ы2 509 612 677 765 703 154 061 426 170 275 897 653 908 Ы2 509 612 677 765 703 154 061 426 170)503[897 653 908 512 509 612 677 765 703) 7 у (Для удобства анализа положения 1 и 7 ключи К; и КЗ выделены в таблице полужирным шрифтом.) В табл. 2 показано, как выбранная нами для примеров последовательность полностью сортируется при помощи этого метода за 11 итераций.
В скобки заключены подмассивы, которые еще предстоит рассортировать; в программе эти подмассивы можно представлять двумя переменными двоичными (1, г) (границы рассматриваемого в данный момент массива) и стеком дополнительных пар (1ы гь), Каждый раз, когда массив разбивается, помещаем в стек больший нз подмассивов и начинаем обрабатывать оставшийся; и так до тех пор, пока не будут получены тривиально короткие массивы, Как показано в уяр. 20, такая процедура гарантирует, что в стеке никогда не будет находиться более 18 г1 элементов. Только что описанную процедуру сортировки можно назвать обменной сортировкой с разделением.
Ее идея принадлежит Ч, Э. Р, Хоару, интереснейшая статья которого [С. А. Н. Ноаге, Сошр..7. 5 (1962), 10-15) — одно из наиболее исчерпывающих из когда-либо опубликованных сообщений об этом методе. Хоар окрестил свой метод "цшс)гэогг" (" быстрая сортировка"), и это название вполне соответствует действительности, так как внутренний цикл вычислений при реализации на любом из современных компьютеров оказывается очень быстрым. При всех сравнениях, выполняемых на текущей итерации„используется один и тот же ключ, так что соответствующее значение можно держать в регистре. Обмен тактами между сравнениями выполняется только в отношении единственного индекса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
