Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 34
Текст из файла (страница 34)
В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструк> сортировку. Так как метод использует разряды ключа, представленного в двоичной системе счисления, назовем его обменной поразрядной сортировкой. В общих чертах этот алгоритм можно описать следующим образом. 1) Последовательность сортируется по сгюаршему значан1ему двоичному разряду так, чтобы все ключи, начинаюпшеся с О, оказались перед всеми ключами„начинающимися с 1. Для этого необходимо найти крайний слева ключ К,, начинающийся с 1, и крайний справа ключ К, начинающийся с О, после чего Л; и Ву поменяются местами, н процесс будет повгоряться, пока не получится 1 > у.
й) Пусть гю — множество элементов, начинающихся с О. а Г~ — множество всех остальных элементов. Ьудем применять к Ре поразрядную сортировку (начав теперь со втиорого бита слева, а не со старшего) до тех пор, пока множество го полностью не рассортируется. Затем проделаем то же самое с Гы Например, в табл. 3 показано, как действует обменная поразрядная сортировка на наши 16 случайных чисел, записанных теперь в восьмеричной системе счисления, В строке итерации 1 показав исходный массив; после обменов по первому биту приходим ко второй итерации. На второй итерации сортнруется первая группа по второму биту, на третьей — по третьему биту.
(Читатель должен мысленно преобразовать восьмеричные числа в 10-разрядные двоичные. Например, ОзУх в двоичном коде будет равно (0 010 011010)э.) Достигнув после сортировки по четвертому биту пятой итерации, обнаруживаем, что в каждой из оставшихся групп содержится всего по одному элементу, так что эту часть массива можно больше не рассматривать. Запись гм[0233 ОЗЫ]" означает, что подмассив 6836 Ойул еще предстоит сортировать по четвертому биту слева. В этом конкретном случае сортировка по четвертому биту не дает ничего нового; чтобы разделить элементы, необходимО добраться до пятого бита.
Весь процесс сортировки, показанный в табл. 3, выполняется за 22 итерации; это несколько больше соответствующего значения при быстрой сортировке (см. табл. 2). Количество операций анализа отдельных разрядов — - 82 — также велкко, но мы увидим, что число такого типа операций при больших Ю в действительности меньше, чем число сравнений при быстрой сортировке, в предположении, что значения ключей имеют равномерное распределение. Общее количество обменов записей в табл. 3 равно 17, т.
е. оно весьма умеренно. Заметим, что, хотя сортируются 10- битовые числа, в данном примере при проверке битов никогда не приходится идти дальше седьмого бита. Как и при быстрой сортировке, для хранения "информации о границах" подмассивов, ожидающих сортировки, можно воспользоваться стеком. Вместо того чтобы сортировать, в первую очередь, наименьший из подмассивов, удобно просто продвигаться слева направо, и размер стека в этом случае никогда не превзойдет числа разрядов в двоичном представлении сортируемых ключей. В алгоритме, приведенном ниже, элемент стека (г,Ь) указывает на то, что подмассив с правой границей г ожидает сортировки по Ь-му разряду; левую границу можно не запоминать в стеке: она всегда задана неявно, поскольку в этой процедуре массив всегда обрабатывается слева направо.
Алгоритм К (Обменная поразрядная соршироака). Записи Вы, Вм перекомпоновываются в пределах той же области памяти. По завершении сортировки их ключи будут упорядоченьп К~ < ° < Кл. Предполагается, что все ключи — гп-разрядные двоичные числа (а~ аз... а,„)ьч (-й по старшинству разряд а; называется "разряд 1" ключа. Необходим вспомогательный стек, вмещающий до пт — 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями, описанной выше.
Возможны некоторые усовершенствования с целью повышения эффективности (они описаны ниже, в тексте раздела и в упражнениях). К1. [Начальная установка.) Очистить стек и установить 1 е- 1, г +- Х, Ь <- 1. К2. [Начать новую итерацию.[ (Теперь желательно рассортировать подмассив В~ ° В.„по разряду 6 в соответствии с алгоритмом 1 < г.) Если 1 = г, перейти к шагу К10 (так как массив, состоящий из одного слова, уже рассортировав). В противном, случае установить 1 с- 1, 1 <- г.
КЗ. [Проверить наличие 1 в К;.) Проверить разряд Ь ключа Кь Если он равен 1, то перейти к шагу Кб. К4. [Увеличить 1.[ Увеличить 1 на 1. Если 1 < у, возвратиться к шагу КЗ; в противном случае перейти к шагу К8. Кб. [Проверить наличие О в Куем[ Проверить разряд 6 ключа Ку+м Если он равен О, то перейти к шагу Ку. Кб. [Уменьшить у.) Уменьшить у на 1.
Если 1 < у, перейти к шагу К5; в противном случае перейти к шагу К8. КT. [Поменять местами „ ч.~.] Поменять местами записи В, +э В.+г и перейти к шагу К4. К8. [Проверить особые случаи.[ (К этому моменту итерация разделения завершена, 1 = у + 1, разряд Ь ключей Кп..., Ку равен О, а разряд Ь ключей К;,..., К, равен 1.) Увеличить Ь на 1. Если 6 > гп, где ш — общее число разрядов в ключах, перейти к шагу К10. (Это означает„что подмассив В~... В„рассортировал. Если в массиве не может быть равных ключей, то такую проверку Таблица 3 ОБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА Стек 0252 1601 ОЗМ 06М 0767 06М 0767 06М 0767 06М 0767 0652 0767 0652 (,) (8,3)(16,2) (4,4)(8,3)(!6,2) «40767 06М Прн поразрвдной обменной еортнровке для оолучення калечного результата нужно веего адин раз нроаналнзмроввть каждый разрвд.
! Х(0767 2 в[0767 3 з40252 4 «40075 5 0075 6 0075 7 Од75 8 0075 9 0075 18 0075 1! 0075 12 0075 13 0075 !4 дд75 15 д075 !6 0075 17 0075 !8 0075 !9 0075 ЯХ 0075 2! 0075 22 0075 23 007Б ои7 Хааа д1й7 0775 ди7 0232 а!27)«[0232 0127 «[0232 ОИ7 з!0232 0127 ОЗМ ОИ7 ОЗМ ОИ7 0232 0127 ОЗМ 0127 0232 0127 0232 ОХ27 0232 0127 0232 0127 0232 0127 0232 0127 0232 ОИ7 дй32 0127 0232 0127 д232 дИ7 ОЙМ 0127 0232 ОИ7 0232 0075 1614 0075 ОЙМ 0075)а[0775 0252[в[0775 0252) а[0775 0252) а[0775 0252 а[0775 дйбй 0423 0252 !ЦЙЗ 0262 0423 0252 д4йЗ ОЗМ ХЦЗЗ РЗБЗ 0423 ОЗМ 0423 0252 0423 0252 0423 0252 042Я 0252 0423 0262 042Я дйбй 0423 ОЗМ 0423 ОЗМ !ЦЗЗ дйбй 0423 ОБМ ь(!!767 0652 е!0767 06М т(0767 0652 д767 06М д767 0652 0767 ОБМ 0767 0652 0767 0652 0767 06М 0767 06БЗ 0767 0652 0767 06М 0767 дбМ 0767 дбМ 0767 0423 12!Б 0423)з[!2!5 0423) 2[1215 0423)'з[!215 «ЦЙЗ) з[!Й!5 !ЦЗЗ) З[И1,5 04 23) з[! 21 5 0775!в[1215 0775!з[12И 0775) з[1 й1 5 0775)![12!5 0775 з!1215 0775 «[12!5 0775 «[[!!44 0775 1дод 0775 1000 0775 1000 0775 1000 0775 !Оао 0775 1000 0775 1000 0775 1000 0775 1000 06М 0232 1601 1614 1601 16Ц 1бд1 16Ц !60! 1614 1601 1614 1601 1Щ 1601 1614 И01 1Щ ИО1 1614 1601 1614 1601 1614 1277 1375 1000$«[1375 1144 «!1375 1144 «11245 1 144 ИХБ П44 1ЙИ 1144 12!5 П44 ИИ 1Ц4 И!5 1ЦБ !ЙИ ! 144 1215 0775 1ддо 1000 1000 1000 1000 1000 1000 1000 1000 ХОРО Иад 1000 1277 1й77 1277 е[! 277 1245 И45 1245 1245 1245 1245 1Ц4 И45 1375 Щ4 1245 1375 П44 И45 И75 П44 1245 1375 Щ4 И45 И75 1ЦБ 1245 1375 1144 1245 1375 1144 1245 1375 П44 Х245 И75 ХЦ4 1245 1375 !!44 И45 1375 1Ц4 1245 И75 1144 !245)а[16!4 1245) з[!614 ии 1245) [1БЦ !й!5) з)! 375[ а[1614 ! 245[[з[1 375 Я1 61 4 1277 1375 «[1614 1277 1375 «(1614 1277 И7Б «41БЦ И77 !375 ой Б!4 1277 1315 т[!б!4 1277 1375 ИО! 1277) ! И77) ! 1277) ! И77! ! 1277) 3 И77) 3 1277) 5 И77) 8 1277) 7 1277) 7 1277[ 7 1277) 9 160!) 9 1601[ 9 1601) !! 1601) !! 160!) !2 160!) !5 !601) !5 1601) ХБ 1601$ !5 Хба!) !5 1614 !7 !6 8 2 4 8 8 8 8 8 !6 14 Ха 14 13 !3 !8 !6 !8 Хб Хб (8,3)(!6,2) (8',3)(18',2) ( .2) (16,2) (18,2) (,2) (16,2) (18,3) (14,4)(!8,3) (!8,3) (!4,5)(!8,3) (!4,5)(!8,3) можно не делать.) В противном случае, если 1 < 1 нли 1 = г, возвратиться к шагу К2 (все просмотренные разряды оказались равными соответственно 1 или О), Если же 1 = 1, то увеличить 1 на 1 н перейти к шагу К2 (встретилсн только один разряд, равный О), КВ.
(Поместить в стек.] Поместить в стек элемент (г, Ь), а затем установить г ~ — 1 и перейти к шагу К2. К10. (Извлечение из стека.] Если стек пуст, значит, сортировка завершена. В противном случае установить 1+- г + 1, извлечь из стека элемент (г', Ь'), установить г+- г', Ь<-Ь> н возвратиться к шагу К2. $ Программа К (()6>кеннан иоразрлдная соршироека). В следующей программе для машины Н11 используются, по существу, те же соглашения, что и в программе Я, Значения регистров таковы: гП гй 1 — г, г12 га г, г13 гй 1, г14 га 1, г15 га гп — Ь, г16 = размер стека, если не учитывать, что в некоторых командах (отмеченных ниже) удобно оставить г13 = 1 — 1' или г14 = 1 — 1. Двоичная природа поразрядной сортировки объясняет использование в этой программе команд ЗВВ (поразрядный сдвиг содержимого АХ вправо), 1АЕ (переход, если содержимое А четко) и 1АО (переход, если содержимое А нечетно), определенных в разделе 4.5.2.
Предполагается, что А» 2. 01 ЗТАВТ ЕМТ6 0 1 0$ ЕМТ1 1-М 1 02 ЕМТ2 М 1 04 ЕМТб Н" 1 1 05 1НР 1Р 1 Н1. Начальная стаи яа. Очистить стек 1 >- 1. > +- К, Ь+- 1. Перейти к шагу К2 (опустить проверку 1 = г). КО. Поместить я стек. (г14 =1 (г,Ь) ю стек. гП +- 1- 1'. г+- 1. К2. Начать нов ю нте яю. (г13 =1-Я ]г13=1-Я > с-1, 1+- г. НЗ.
П ве ять наля ие 1 в К. Н4. Увеличить >, > +- >+ 1. (г13=1-1] Перейти к а>агу КЗ, если > < 1. (г13 =1-2) г13+- А 00 9Н 07 ОВ 00 10 11 1Н 12 12 ЗН 14 15 10 17 6Н 10 10 бН 20 21 йй 32 7Н 24 25 66 27 4Н 2В 20 1МС6 1 ЗТ2 ЗТАСК,6(А) ЗТб ЗТАСК,б(В) ЕММ1 0,4 ЕМТ2 -1,3 ЕМТЗ 0,1 ЕМТ4 0,2 1МСЗ 0.4 10А 1МРУТ,З ЗВВ 0,5 ЛАЕ 4Р ОЕС4 1,3 14М ВР 1МС4 О,З 1.РА 1МРОТ+1>4 ЗВВ 0,5 ЮАО 6В 10А 1МРОТ+1>4 ЫХ 1МРОТ,З ЗТХ 1МРОТ+1,4 ЗТА 1МРОТ,З ОЕСЗ -1,4 ЛЗМР ЗВ 1МСЗ 0,4 Я Я Я Я Я А А С> С> С> С> С" + Х С" + Х С" С" С» С" В В В В С' — Х С' — Х А — Х Младший разряд гА +- разряд Ь ключа К;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
