Структуры данных и алгоритмы (1021739), страница 64
Текст из файла (страница 64)
Разберемся с циклом в строках (3), (4), осуществляющих конкатенациюсписков. Сначала временно предположим, что указатели на концы списков существуют. Тогда строка (4) выполняется за фиксированное время, а весь цикл требуетвремени порядка О(т). Следовательно, в этом случае вся программа выполняетсяза время О(п + т).Если указатели на концы списков не используются, тогда в строке (4) до началанепосредственного процесса слияния списка B[v] со списком B[lowkey] необходимопросмотреть все элементы списка B[v], чтобы найти его конец. Заметим, что конецсписка B[lowkey] искать не надо, он известен.
Дополнительное время, необходимоедля поиска концов всех "карманов", не превышает О(п), поскольку длина всех"карманов" равна п. Это дополнительное время не влияет на порядок времени выполнения всей процедуры binsort, поскольку О(п) не больше, чем О(п + т).Сортировка множеств с большими значениями ключейЕСЛИ количество различных ключей т не превосходит количества элементов п, товремя выполнения О(п + т) программы из листинга 8.12 в действительности будетиметь порядок О(п).
Но каково будет это время, если т = п2, например? Повидимому, если время выполнения программы О(п + т), то должно быть О(п + п2),т.е. ОСи2).1 Но можно ли учесть тот факт, что множество значений ключей ограничено, и улучшить время выполнения программы? Ответ положительный: приведенныйниже алгоритм, являющийся обобщением "карманной" сортировки, даже на множестве значений ключей вида 1, 2, ..., п* для некоторого фиксированного'k выполняетсортировку элементов за время О(п).Пример 8.6.
Рассмотрим задачу сортировки п целых чисел из интервала от 0 дол2 - 1. Выполним сортировку этих чисел в два этапа. На первом этапе используем п"карманов", индексированных целыми числами от 0 до п - 1. Поместим каждое сортируемое число i в список "кармана" с номером i mod п. Но в отличие от процедурылистинга 8.12 каждый новый элемент помещается не в начало списка, а в его конец,и это очень важное отличие.
Заметим, что если мы хотим эффективно выполнитьвставку элементов в конец списков, то надо для представления списков использоватьсвязанные списки, а также указатели на концы списков.Например, пусть п = 10, а список сортируемых чисел состоит из точных квадратов от О2 до 92, расположенных в случайном порядке 36, 9, 0, 25, 1, 49, 64, 16, 81, 4.В этом случае номер "кармана" для числа i равен самой правой цифре в десятичной записи числа i. В табл.
8.5,а показано размещение сортируемых чисел по спискам "карманов". Отметим, что числа появляются в списках в том же порядке, вкаком они расположены в исходном списке, например в списке "кармана" 6 будутрасполагаться числа 36, 16, а не 16, 36, поскольку в исходном списке число 36предшествует числу 16.1Так как по ранее сделанным предположениям значения ключей имеют перечислимый типданных, а в языке Pascal всегда можно объявить собственный перечислимый тип, то в данномслучае можно объявить тип данных, содержащий все значения ключей.
После этого программаиз листинга 8.12 будет выполняться за время О(п + т). Но такой подход имеет очевидные недостатки: во-первых, надо перечислить все значения ключей (если их несколько сотен, то этоможет породить определенные проблемы), во-вторых, значения ключей должны быть записаныв возрастающем порядке, т.е.
необходимо провести предварительную сортировку ключей, и, втретьих, программа с таким объявлением типа будет работать только на данном множествеключей. Именно эти соображения приводят к необходимости модификации алгоритма"карманной" сортировки. — Прим. ред.250ГЛАВА 8. СОРТИРОВКАТеперь содержимое "карманов" поочередно объединим в один список:О, 1, 81, 64, 4, 25, 36, 16, 9, 49.(8.10)Если в качестве структуры данных мы использовали связанные списки, а также указатели на концы списков, то операция конкатенации п элементов, содержащихся вкарманах, займет время порядка О(п).Целые числа из списка, созданного путем конкатенации на предыдущем этапе,снова распределяются по карманам, но уже по другому принципу. Теперь число iпомещается в карман с номером [i/л], т.е. номер кармана равен наибольшему целомучислу, равному или меньшему 1/п (другими словами, квадратные скобки здесь и далее в этой главе обозначают операцию взятия целой части числа).
На этом этапе добавляемые в "карманы" числа также вставляются в концы списков. После распределения списков по "карманам" снова выполняется операция конкатенации всех списков в один список. В результате получим отсортированный список элементов.В табл. 8.21,6 показан список (8.10), распределенный по "карманам", в соответствии с правилом, когда число i вставляется в "карман" с номером [i/n].Таблица 8.5. Двухэтапная „карманная" сортировка"Карман"Содержимое"Карман"Содержимое00010, 1, 4, 9222533364911,81464, 445255636, 1666477889169, 49819Чтобы увидеть, почему этот алгоритм работает правильно, достаточно заметить,что когда числа помещаются в один "карман", например числа О, 1, 4 и 9 — в карман 0, то они будут располагаться в возрастающем порядке, поскольку в списке(8.10) они упорядочены по самой правой цифре.
Следовательно, в любом "кармане"числа также будут упорядочены по самой правой цифре. И, конечно, распределение чисел на втором этапе по "карманам" в соответствии с первой цифрой гарантирует, что в конечном объединенном списке все числа будут расставлены в возрастающем порядке.Покажем правильность работы описанного алгоритма в общем случае, предполагая, что сортируемые числа являются произвольными двузначными целыми числамииз интервала от 0 до п2 - 1. Рассмотрим целые числа i = an + Ь и ;' = en + d, где всечисла а, Ь, с и d из интервала от 1 до п - 1. Пусть I < j. Тогда неравенство а > с невозможно, поэтому а < с. Если а < с, тогда на втором этапе сортировки число i будетнаходиться в "кармане" с меньшим номером, чем номер "кармана", в котором находится число j, и, следовательно, в конечном списке число i будет предшествоватьчислу j. Если а = с, то число Ь должно быть меньше, чем d.
Тогда в объединенномсписке после первого этапа сортировки число i будет предшествовать числу j, поскольку число i находилось в "кармане" с номером Ь, а число / — в кармане с номе8.5. "КАРМАННАЯ" СОРТИРОВКА251ром d. На втором этапе числа i и / будут находиться в одном "кармане" (так кака = с), но число i будет вставлено в список этого "кармана" раньше, чем число j.Поэтому и в конечном списке число i будет предшествовать числу j. DОбщая поразрядная сортировкаПредположим, что тип данных ключей keytype является записями со следующими полями:typekeytype = recordday: 1..31;month: (jan, ..., dec);year: 1900..1999end;(8.11)либо массивом элементов какого-нибудь типа, напримерtypekeytype = array[1..10] of char;(8.12)Далее будем предполагать, что данные типа keytype состоят из k компонентfi.
fa, ••-, fk типа ti, t2tk. Например, в (8.11) ti = 1..31, (2 = (Jan, ..., dec), at3 = 1900..1999. В (8.12) k = 10, a fi = *2 = ••• = *t = char.Предположим также, что мы хотим сортировать записи в лексикографическом порядке их ключей. В соответствии с этим порядком ключевое значение (ai, а2, ..., at) меньшеключевого значения (6Ь Ь2, ..., bk), где а/ и fc, — значения из поля / ( (i = 1, 2, ..., k), есливыполняется одно из следующих условий:1. CLi < bi, ИЛИ2. di = bi и а 2 < &2>илиk. ai = bi, а2 — b%, ..., a/f-i = fet_j и a* < & A .Другими словами, ключевое значение (aj, a2, ..., ak) меньше ключевого значения(bi, Ь2, ..., bk), если существует такой номер j (1 < j<k - 1), что a t = bi, a2 = 62» •••> aj = fyи dj+i < bi+1.Если принять сделанные выше определения ключей, то в этом случае значенияключей можно рассматривать как целочисленные выражения в некоторой системесчисления.
Например, определение (8.12), где каждое поле ключа содержит какойлибо символ, позволяет считать эти символы целочисленными выражениями по основанию 128 (если использовать только латинские буквы) или, в зависимости от используемого набора символов, по какому-то другому основанию. В определении типов(8.11) значения поля year (год) можно считать целыми числами по основанию 100(так как здесь значения поля изменяются от 1900 до 1999, т.е. могут изменятьсятолько последние две цифры), значения поля month (месяц) очевидно можно интерпретировать как целочисленные выражения по основанию 12, а значения третьегополя day (день) — как целочисленные выражения по основанию 31.
Предельныйслучай такого подхода: любые целые числа (из конечного фиксированного множества) рассматриваются как массивы цифр по основанию 2 или другому подходящемуоснованию. Обобщение "карманной" сортировки, использующее такое видение значений ключевых полей, называется поразрядной сортировкой.Основная идея поразрядной сортировки заключается в следующем: сначала проводится "карманная" сортировка всех записей по полю Д (как бы по "наименьшейзначащей цифре"), затем отсортированные по "карманам" записи объединяются(наименьшие значения идут первыми), затем к полученному объединенному списку252ГЛАВА 8.
СОРТИРОВКАприменяется "карманная" сортировка по полю Д_ 1( снова проводится конкатенациясодержимого "карманов", к объединенному списку применяется "карманная" сортировка по полю fk-2, и т.д. Так же, как и в примере 8.6, при сортировке записей по"карманам" новая запись, вставляемая в карман, присоединяется в конец спискаэлементов этого "кармана", а не в начало, как было в "чистой карманной" сортировке. После выполнения "карманной" сортировки по всем ключам ft, / t _ lf ..., Д и последнего объединения записей получим их результирующий список, где все записибудут упорядочены в лексикографическом порядке в соответствии с этими ключами.Эскиз описанного алгоритма в виде процедуры radixsort (поразрядная сортировка)приведен в листинге 8.13.
Для обоснования этого алгоритма можно применить методику, показанную в примере 8.6.Листинг 8.13. Поразрядная сортировка(1)(2)(3)(4)(5)(6)(7)procedure radixsort;{ radixsort сортирует список А из п записей по ключевым полямf\, £2, ..., fk типов fci, ta, .-., tjc соответственно. В качестве"карманов" используются массивы Bj типаarray[til of listtype, 1 < i < k, где listtype — тип данныхсвязанных списков записей }beginfor i:= k downto 1 do beginfor для каждого значения v типа ti do{ очистка "карманов" }сделать Bj[v] пустым;for для каждой записи г из списка A doпереместить запись г в конец списка "кармана" Bj[v],где v — значение ключевого поля fi записи г;for для каждого значения v типа tjв порядке возрастания v doконкатенация Sj[v] в конец списка Аendend; { radixsort }Анализ поразрядной сортировкиПредполагаем, что для эффективного выполнения поразрядной сортировки применяются подходящие структуры данных.
В частности, предполагаем, что списоксортируемых элементов представлен в виде связанного списка, а не массива. Но напрактике можно использовать и массив, если добавить еще поле связи типа геcordtype для связывания элементов A[i\ и A[i + 1] для i = 1, 2, ..., п - 1. Таким способом можно создать связанный список в массиве А за время порядка О(п). Отметимтакже, что при таком представлении элементов нет необходимости в их копированиив процессе выполнения алгоритма, так как для перемещения записей из одного списка в другой достаточно изменить значения поля связи.Как и ранее, для быстрого выполнения операции конкатенации будем использовать указатели на конец каждого списка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
