Главная Промышленная автоматика.

ром d. На втором этапе числа i и / будут находиться в одном "кармане" (так как а = с), но число i будет вставлено в список этого "кармана" раньше, чем число j. Поэтому и в конечном списке число i будет предшествовать числу j. □

Общая поразрядная сортировка

Предположим, что тип данных ключей keytype является записями со следующими полями:

type

keytype = record day: 1. .31;

month: (jan, dec);

year: 1900.. 1999 end; (8.11)

либо массивом элементов какого-нибудь типа, например

type

keytype = array[1..10] of char; (8.12)

Далее будем предполагать, что данные типа keytype состоят из к компонент h<fa, •,fk типа fi, . . . tn- Например, в (8.11) ti = 1..31, = (Jan, dec), a *3 = 1900..1999.B (8.12) A:= 10, а«1=*2= = *t = char.

Предполоким также, что мы хотим сортировать записи в лексикографическом порядке их ключей. В соответствии с этим порядком ключевое значение (oi, 02, а) меньше ключевого значения (bi, йг. &*). где nfc, - значения из поля (i = 1, 2, к), если выполняется одно из следующих условий:

1. fli < 61, или

2. ai = biM < 62. или

к. Й! = bi, аз - Й2. fflt-i=fet JH < й.

Другими словами, ключевое значение (ai, 02, а) меньше ключевого значения (bi, 62. ft*), если сушествует такой номер J (1 <j <k - 1), что Ui = bi, = 62» •"> a/=fy

и a/+l <

Если принять сделанные выше определения ключей, то в этом случае значения ключей мокно рассматривать как целочисленные выражения в некоторой системе счисления. Например, определение (8.12), где каждое поле ключа содержит какой-либо символ, позволяет считать эти символы целочисленными выражениями по основанию 128 (если использовать только латинские буквы) или, в зависимости от используемого набора символов, по какому-то другому основанию. В определении типов (8.11) значения поля year (год) можно считать целыми числами по основанию 100 (так как здесь значения поля изменяются от 1900 до 1999, т.е. могут изменяться только последние две цифры), значения поля month (месяц) очевидно мокно интерпретировать как целочисленные выражения по основанию 12, а значения третьего поля day (день) - как целочисленные выражения по основанию 31. Предельный случай такого подхода: любые целые числа (из конечного фиксированного множества) рассматриваются как массивы цифр по основанию 2 или другому подходящему основанию. Обобщение "карманной" сортировки, использующее такое видение значений ключевых полей, называется поразрядной сортировкой.

Основная идея поразрядной сортировки заключается в следующем: сначала проводится "карманная" сортировка всех записей по полю Д (как бы по "наименьшей значащей цифре"), затем отсортированные по "карманам" записи объединяются (наименьшие значения идут первыми), затем к полученному объединенному списку



применяется "карманная" сортировка по полю снова проводится конкатенация содержимого "карманов", к объединенному списку применяется "карманная" сортировка по полю fit-2, и т.д. Так же, как и в примере 8.6, при сортировке записей по "карманам" новая запись, вставляемая в карман, присоединяется в конец списка элементов этого "кармана", а не в начало, как было в "чистой карманной" сортировке. После выполнения "карманной" сортировки по всем ключам /t, Д и последнего объединения записей получим их результирующий список, где все записи будут упорядочены в лексикографическом порядке в соответствии с этими ключами. Эскиз описанного алгоритма в виде процедуры radixsort (поразрядная сортировка) приведен в листинге 8.13. Для обоснования этого алгоритма можно применить методику, показанную в примере 8.6.

Листинг 8.13. Поразрядная сортировка

procedure radixsort ;

{ radixsort сортирует список А из п записей по ключевьм пол51м

f\, f2, f;c ТИПОВ fci, t2, tj: соответственно. В качестве

"карманов" используются массивы Bi типа

array! tv] of listtype, 1 < i < к, где listtype - тип данных связанных списков записей } begin

(1) for i:= к downto 1 do begin

(2) for для каждого значения v типа ti do

{ очистка "карманов" }

(3) сделать Bilv] пустым;

(4) for для каждой записи г из списка А do

(5) переместить запись г в конец списка "кармана" Bi[v] ,

где V - значение ключевого поля fi записи г;

(6) for для каждого значения v типа tj

в порядке возрастания v do

(7) конкатенация Bilv] в конец списка А end

end; { radixsort }

Анализ поразрядной сортировки

Предполагаем, что для эффективного выполнения поразрядной сортировки применяются подходящие структуры данных. В частности, предполагаем, что список сортируемых элементов представлен в виде связанного списка, а не массива. Но на практике можно использовать и массив, если добавить еще поле связи типа recordtype для связывания элементов A[i] и Afi + 1] для / = 1, 2, п - \. Таким способом можно создать связанный список в массиве А за время порядка 0(п). Отметим также, что при таком представлении элементов нет необходимости в их копировании в процессе выполнения алгоритма, так как для перемещения записей из одного списка в другой достаточно изменить значения поля связи.

Как и ранее, для быстрого выполнения операции конкатенации будем использовать указатели на конец каждого списка. Тогда цикл в строках (2), (3) листинга 8.13 выполняется за время 0(s,), где s, - число различных значений типа t,. Цикл строк (4), (5) требует времени порядка 0(п), цикл строк (6), (7) - 0(s,). Таким образом, общее время выполнения поразрядной сортировки составит

jO(Sj + п), т.е. 0(fere-l-jS,), или, если А: константа, 0(ге-i-* 8,).

Пример 8.7. Если ключи являются целыми числами из интервала от О до л* - 1 для некоторой константы к, то можно обобщить пример 8.6 и рассматривать ключи как целые числа по основанию п, состоящие из не более чем к "цифр". Тогда для



всех i, 1 < i < А, t, - целые числа из интервала от О до я - 1 и «, = п. В этом случае выражение + ) примет вид 0(п + kn), которое имеет порядок 0(п), поскольку к - константа.

Другой пример: если ключи являются символьными строками фиксированной

длины k, тогда для всех ; S; = 128 (например) и X*=i*i" будет константой. Таким образом, алгоритм поразрядной сортировки по символьным строкам фиксированной длины выполняется за время 0(п). Фактически, если к - константа и все S( являются константами (иди если даже имеют порядок роста 0(п)), то в этом случае поразрядная сортировка выполняется за время порядка 0(л). Но если к растет вместе с ростом п, то время выполнения поразрядной сортировки может отличаться от 0(л). Например, если ключи являются двоичными числами длины log га, тогда А = log и и Si = 2 для всех В таком случае время выполнения алгоритма составит 0(п logn). П

8.6. Время выполнения сортировок сравнениями

Существует "общеизвестная теорема" (из математического фольклора), что для сортировки п эдементов "требуется времени п logre". Как мы видели в предыдущем разделе, это утверждение не всегда верно: если тип ключей такой, что значения ключей выбираются из конечного (по количеству эдементов) множества (это позволяет с "пользой" применить метод "карманной" иди поразрядной сортировки), тогда для сортировки достаточно времени порядка 0(л). Однако в общем случае мы не можем утверждать, что ключи принимают значения из конечного множества. Поэтому при проведении сортировки мы можем опираться только на операцию сравнения двух значений ключей, в результате которой можно сказать, что одно ключевое значение меньше другого.

Читатель может заметить, что во всех алгоритмах сортировки, которые мы рассмотрели до раздела 8.5, истинный порядок эдементов определялся с помощью последовательных сравнений значений двух ключей, затем, в зависимости от результата сравнения, выполнение алгоритма шло по одному из двух возможных путей. В противоположность этому, алгоритм, подобный показанному в примере 8.5, за один шаг распределяет п эдементов с целочисленными значениями ключей по п "карманам", причем номер "кармана" определяется значением ключа. Все программы раздела 8.5 используют мощное средство (по сравнению с простым сравнением значений) языков программирования, позволяющее за один шаг находить в массиве по индексу местоположение нужной ячейки. Но это мощное средство невозможно применить, если тип данных ключей соответствует, например, действительным числам. В языке Pascal и в большинстве других языков программирования нельзя объявить индексы массива как действительные числа. И если даже мы сможем это сделать, то операцию конкатенации "карманов", номера которых являются машинно-представимыми действительными числами, невозможно будет выполнить за приемлемое время.

Деревья решений

Сосредоточим свое внимание на алгоритмах сортировки, которые в процессе сортировки используют только сравнения значений двух ключей. Можно нарисовать двоичное дерево, в котором узды будут соответствовать "состоянию" программы после определенного количества сделанных сравнений ключей. Узды дерева можно

Но в этом случае, если двоичные числа длины logre можно трактовать как одно слово, лучше объединить поля ключей в одно поле типа и использовать обычную "карманную" сортировку.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 [80] 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002