AOP_Tom3 (1021738), страница 49
Текст из файла (страница 49)
Метод, который даст абсолютную гарантию того, что в худшем случае время сортировки будет составлять порядка 0(1У 1ой Ф) и одновременно будет обеспечена высокая скорость в среднем, можно получить, комбинируя метод быстрой сорти- ровки с некоторыми другими схемами. Например, Д. Р.
Муссер 1см. 1>. Н. Мпэзег ЯоГгиаге Ргасг>се й Ехрег. 27 (1997), 983-993) пречложил ввести в каждый элемент стека быстрой сортировки еще и компонент "глуб>ина разделения". Если найден подмассив, который разделен более чем, скажем, 218Х раз, предлагается прекратить выполнение алгоритма Я и переключиться на алгоритм 5.2.3Н. В таком случае сохраняется то же время выполнения внутреннего цикла, а следовательно, и среднее время выполнения сортировки.
Роберт Седгевик проанализировал множество оптимизированных вариантов быстрой сортировки и Асса 1пГогтабса 7 (1977), 327-356, и в САСМ 21 (1978), 847-857, 22 (1979), 368. Версии бьк:трой сортировки, включенные в библиотеку программ Н1ч!Хе, которая создавалась в течение 15 лет, описана в работе 3. Ь. Вепг1еу апд М. В. МсВгоу, БоГ1>гаге Ргасбге м Ехрег. 23 (1993), 1249 — 1265. Обменная поразрядная сортировка. Рассмотрим метод, совершенно отличный от всех схем сортировки, которые описывались до сих пор.
В нем используется двоичное предсп>явление ключей, и потому он предназначен только для двоичных компьютеров. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли 0 или 1 отдельные разряды ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку.
Так как метод использует разряды ключа, представленного в двоичной системе счисления, на>овем его обменной поразрядной сортировкой. В общих чертах этот алгоритм можно описать следующим образом. >) Последовательность сортируется по с>падшему значащему двоичному разряду так, чтобы все ключи, начинающиеся с О„оказались перед всеми ключами, начинающимися с 1. Для этого необходимо найти крайний слева ключ К„начинаю>цийся с 1, и крайний справа ключ К>, начинающийся с О, после чего Рм и В> поменяются местами, и процесс будет повторяться, пока не получится > ) 1. й) Пусть ге — множество элеменгов, начинающихся с О, а Р> -- множество всех осильных элементов.
Будем применять к Ке поразрядную сортировку (начин теперь со второго бита слева, а не со старшего) до тех пор, пока множество Ре полностью не рассортируется. Затем проделаем то же самое с Р>. Например, в табл. 3 показано, как действует обменная поразрядная сортировка на на>пи 16 с»учайных чисел, записанных теперь в восьмеричной системе счисления. В строке итерации 1 показан исходный массив; после обменов по первому биту приходим ко второй итерации. На второй итерации сортируется первая группа по второму биту, на третьей — по третьему биту. (Читатель должен мысленно преобразовать восьмеричные числа в 10-разрядные двоичнь>е.
Например, 0ззй в двоичном коде будет равно (0010011010)з.) Достигнув после сортировки по четвертому биту п>ггой итерации, обнаруживаем, что в каждой из оставшихся групп содержится всего по одному элементу, так что эту часть массива можно болыпе не рассматривать. Запись "«(0932 0258)" означает, что подмассив ОзЫ ОзЫ еще предстоит сортировать по четвертому биту слева.
В этом конкретном случае сортировка по четвертому биту не дает ничего нового; чтобы разделить элементы, необходимо добраться до пятого бита. Весь процесс сортировки, показанный в табл. 3, выполняется за 22 итерация; это несколько больше соогиетствующего значения при быстрой сортировке (см. табл. 2). Количество операций анализа отдельных разрядов — 82 — также велико, но мы увидим, что число такого типа операций при больших Аь в действительности меньше, чем число сравнений при быстрой сортировке, в предположении, что значения ключей имеют равномерное распределение. Общее количество обменов записей в табл.
3 равно 17, т. е. оно весьма умеренно. Заметим, что, хотя сортируются 10- битовые числа, в данном примере при проверке битов никогда не приходится идти дальше седьмого бита. Как и при быстрой сортировке, для хранения "информации о границах" подмассивов, ожидающих сортировки, можно воспользоваться стеком.
Вместо того чтобы сортировать, в первую очередь, наименьший из подмассивов, удобно просто продвигаться слева направо, и размер стека в этом г ьучае никогда не превзойдет числа разрядов в двоичном представлении сортируемых ключей. В алгоритме, приведенном ниже, элемент стека (г, Ь) указывает на то, что подмассив с правой границей г ожидает сортировки по Ь-му разряду; левую граььицу можно не запоминать в стеке; она всегда задана неявно, поскольку в этой процедуре массив всегда обрабатывается слева направо. Алгоритм К (Обменная ььоразрядная сорглировка). Записи Вь,, Вн перекомпоновываются в пределах той же области памяти. По завершении сортировки их ключи будут упорядочены: Кь « Ки.
Предполагается, что все ключи —. ьп-разрядные Двоичные числа (аь аь... аьн)ьй ь-й по стаРшинствУ РазРЯд а, называетсЯ "РазРЯд ь" ключа. Необходим вспомогательный стек, вмепьающий до пь — 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями, описанной выше. Возможны некоторые усовершенствования с целью повышения эффективности (они описаны ниже, в тексте раздела и в упражнениях). К1. (Начальная установка.] Очистить стек и установить 1» — 1, г +- Аь, Ь +- 1. К2. ]Начать новую итерацию.] (Теперь желательно рассортировать подмассив Вь ... В„по разряду Ь в соответствии с алгоритмом 1 < г.) Если 1 = г, перейти к шагу В10 (так как массив, состоящий из одного слова, уже рагсортирован).
В противном. случае установить ь »- 1, у +- г. КЗ. (Проверить наличие 1 в К,.] Проверить разряд Ь ключа Кь. Если он равен 1, то перейти к шагу Вб. В4. ]Увеличить ь.] Увеличить ь на 1. Если ь < ь', возвратиться к шагу ВЗ; в противном случае перейти к шагу В8. Кб. ]Проверить наличие 0 в К+».] Проверить разряд б ключа К +,. Если он равен О, то перейти к шагу В7. К6. [Уменьшить ь1] Уменьшить ь на 1. Если ь < у', перейти к шагу В5; в противном случае перейти к шагу В8. К7.
(Поменять местами Вн В +ь.] Поменять местами записи В, »-ь В +ь и перейти к шагу В4. К8. (Проверить особые случаи.] (К этому моменту итерация разделения завершена, ь = у+ 1, разряд Ь ключей Кь,..., К равен О, а разряд Ь ключей Кн..., К, равен 1.) Увеличить Ь на 1. Если Ь ) т, где т — общее число разрядов в клкьчах, перейти к шагу В10. (Это означает, что подмассив Ль... В„рассортирован. Если в ь»ассиве не может быть равных ключей, то такую проверку !$ф $1!! !1! СЯ С? а" »О" Р» 30 ч ?я .» ?о а о ?о с» аос и»»ас- а Ф.
3- 3- а в о? »»Р»»»»»»» ° » ооааооРРРОО Ф» С» Я» Р» Ф„Р» СЧ С' » С» Р» Ф Ф» Ф»» 'О О » О С- РФ» Ф, » Ф3 Ф? О»»» Ф3 Ф3 Ф3 Ф3 ЯЧ Ф Х о а а о о м х о Х й С О„ ?О о х ° ~ х х о ьььоо ФС СЧ Ь О4 Ф? Ф ? Ф3 » Ф? СЧ С» » сс 4'» ь-;-Ф с» о Ф4 Ф4 а» о СФ о О о с» оосььаоос оььоос ос ьсаоос » 'О Ю СЧ Ь С С» Р» Ф» $ Ф? с'4 ООС » Ф4 СЧ Р» Ф? Ь Ф Ь О »» Ф4 ФС -а " '»» О Осс » О СЧ Ф4 Ф4 Ф? »»» 3 4 соса 3 3 » Ц'» "»»» - » О О О О О О С О ь ь сч о »»» ?Ф О о С?С»с ОЬС» 3- 4- Ф.
Ь О О О» О»»» 'О 'О О Осссаа Ч»» Ф» С'\» Р» СЧ Ь Ф3 Ю ось~оса 33 С'4 Ф4 Ф4 Ь Ф3 Р? »»» О Ф4 Ф? Ф3 Ф4 Ф3 Ф? Осссса 44 Ф3 ЯЧ ЯЯ оьььь СФ 'о О О СФ Оооо Р4 Ф3 » О О с.'4 й 3 ааааа » 3 с» о ь й Ж » Ф? СЯ С» Я4 ЯЯ Оса с» ч» о СО с» Ф? Я4 СЧ Ф» С'» Р, О3 О4 СЧ 'О О с- Р' с- Ф? Ф3 Ф? О СО С» Ф Ф О О ю СЧ Ф4 Ось счоо ж .- СО а а СЧ СЧ СС С? о О?-?юо а С4 С? а о Р» .Ф о а 3- сч «»» а Р» с о а 3 С 4 3 4 4 4 4 3 С С 4 ьРС ьоььооРРьсаассссссс СЯ СЯ СЧ Ф3 Ф3 Ф? СЧ Ф3 СЧ Ф? Ф? ?4 Ф О Ь »о О О Ф О О ° »О а О О О ь а с Ь а О О О о о Р о о О О О а а О о О О О с о ь о а а а с О О о О ь О с с сч сч а О а »О о а с о ь О с ь а О О о О Ф 4 О О О О О Р О О ЯЧ о с о О с о о о Ф ' 'с о ° ?о аььс-3 Ф.ььс-с-с Р. О с» о а ь с О О О о ь Р3 СЧ О3 Ф4 Ф4 Ф4 Ф? СЯ СЧ С4 44 М О»»» О 0»»»»»» О Ф Ф О О О О Ььссаас » СЧ Р» Ф? Р»»» 4" С» С'»» Р\ Ф3 Ф4 ФС Ф3 Ф? Ф? Ф3 М Ф? О4 ЯЯ СЯ с» ~с О о ~а а о с» О О с» о Ф? Ф4 44 Ф4 Ф4 СЯ Ф4 Ф4 СЧ Ф4 СЯ Р4 «ч »о а ь ь ь ь »О ь ь а ь ь сч а с4 О о сч сч ь сч сч сч оосьаоааооос СЧ Ф4 Ф4 44 СЧ СЧ Ф3 Ф3 Сч Ф? С.'4 ЯЧ СЯ СЧ Сч Ф3 С'» С'» Р» Ф\ Я'» Р» С'» СЧ» \ С ' С "? СЧ Ф» О Ь О О О Ь О О Ь О О О Ь О О ЯЧ Ф$ СЧ 44 Ф3 Ф? СЧ Ф4 Ф4 Ф3 СЯ РС С'3 Ф? О4 Ф? оььоьаьььо яч Ф4 Ф? Р4 я? яс а Ф? Ф3 ся яч Ф? сч Ф3 Ф4 я4 О О О О О Ь Ь О О О Ь О О О О » О»»» .» ° О»»»»» .»»» ." » ОРРРРоььРРОООС-3 ььь О ь ь о ь О О а О О О ь о о О о ь О ь О О О О О о О О О Ь а О о о О О О а х О а Ц а х х О О О ф О.
О О х х у 5 О й О О о й »О О О а х Д О С» с О а х можно не делать.) В противном случае, если 1 < 1 или 1 = г, возвратиться к шагу К2 (все просмотренные разряды оказались равными соответственно 1 или 0). Если же 1 = 1, то увеличить 1 на 1 и перейти к шагу К2 (встретился только один разряд, равный 0).
В.9. [Поместить в стек.) Поместить в стек элемент (г, 6), а затем установить г « — 1 и перейти к шагу В2. К10. [Извлечение из стека.] Если стек пуст, значит, сортировка завершена. В противном случае установить 1 « — г + 1, извлечь из стека элемент (г', 6'), установить г « — г', 6+- Ь' и возвратиться к шагу 3,2.
1 Программа К (Обменная поразрядная саргпироека). В следующей программе для машины М1Х используются, по сущестну, те же соглашения, что и в программе (4. Значения регистров таковы: гП = 1 — г, г12 = г, г13 н— в «, г14 = 1', г15 = гп — 6, г18 = размер стека, если не учитывать, что в некоторых командах (отмеченных ниже) удобно оставить г13 = ь' — 1' или г14 = 1 — «. Двоичная природа поразрядной сортировки объясняет использование в этой программе команд БНВ (поразрядный сдвиг содержимого АХ вправо), ЗАЕ (переход, если содержимое А четно) и ЛАО (переход, если содержимое А нечетно), определенных в разделе 4.5.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
