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