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


Конец

Рис. 8.4. Конкатенация связанных списков

Теперь можно написать программу "карманной" сортировки записей, когда поле ключей является перечислимым типом. Эта программа, показанная в листинге 8.12, написана с использованием базовых операторов, выполняемых над списками. Как уже говорилось, связанные списки являются предпочтительной реализацией "карманов", но, конечно, можно использовать и другие реализации. Напомним также, что в соответствии с нашими предположениями, массив А типа аггау[1..п] of ге-codrtype содержит элементы, подлежащие сортировке, а массив В типа аг-ray[keytype] of listtype предназначен для "карманов". Будем также считать, что переменные перечислительного типа keytype могут изменяться в пределах от lowkey (нижний ключ) до highkey (верхний ключ).

Листинг 8.12. Профамма Ainso/t („карманная сортировка)

procedure binsort;

{ Сортирует элементы массива А, помещая отсортированный список в "карман" В[lowkey] }

begin

i: integer; V: keytype;

end;

{ начинается занесение записей в "карманы" } for i;= 1 to n do

{ помещение элементаA[i] в начало "кармана",

соответствуищего ключу этого элемента } INSERT(A[i], FIRST(В[А[i].iey]), B[A[i].key]); for v:= suae {lowkey) to highkey do

{конкатенация всех "карманов" в конец "кармана" B[lowkey]} CONCATENATE (В [ lowkey] , B[v]) { binsort }

Анализ „карманной" сортировки

Если сортируется п элементов, которые имеют т различных значений ключей (следовательно, т различных "карманов"), тогда программа из листинга 8.12 выполняется за время порядка 0(п + т), если, конечно, используется подходящая струк-

Для читателя, незнакомого с языком Pascal (или мало знакомого с этим языком), поясним, что применяемая в этом листинге стандартная функция Pascal succ(x) для данных перечислимого типа возвращает следующее за х значение. - Прим. ред.



тура данных. В частности, если т < п, то сортировка выполняется за время 0(п). В качестве "подходящей" структуры данных мы считаем связанные списки. Указатели на концы списков, показанные на рис. 8.4, полезны, но не обязательны.

Цикл в строках (1), (2) листинга 8.12, помещающие записи в "карманы", выполняется за время порядка 0(п), поскольку оператор INSERT в строке (2) требует фиксированного времени, так как вставка записей всегда осуществляется в начало списков. Разберемся с циклом в строках (3), (4), осуществляющих конкатенацию списков. Сначала временно предположим, что указатели на концы списков существуют. Тогда строка (4) выполняется за фиксированное время, а весь цикл требует времени порядка 0(т). Следовательно, в этом случае вся программа выполняется за время 0(п + т).

Если указатели на концы списков не используются, тогда в строке (4) до начала непосредственного процесса слияния списка B[v] со списком B[lowkey] необходимо просмотреть все элементы списка Bfv], чтобы найти его конец. Заметим, что конец списка B[lowkey] искать не надо, он известен. Дополнительное время, необходимое для поиска концов всех "карманов", не превышает 0(п), поскольку длина всех "карманов" равна п. Это дополнительное время не влияет на порядок времени выполнения всей процедуры binsort, поскольку 0(п) не больше, чем 0(п + т).

Сортировка множеств с большими значениями ключей

ЕСЛИ количество различных ключей т не превосходит количества элементов п, то время вьшолнения 0(п + т) программы из листинга 8.12 в действительности будет иметь порядок 0(п). Но каково будет это время, если т = п, например? По-видимому, если время выполнения программы 0(п + т), то должно быть 0(п + п), т.е. 0{п)} Но можно ли учесть тот факт, что множество значений ключей ограничено, и улучшить время выполнения программы? Ответ положительный: приведенный ниже алгоритм, являюшийся обобщением "карманной" сортировки, даже на множестве значений ключей вида 1, 2, л* для некоторого фиксированного/! выполняет сортировку элементов за время 0(п).

Пример 8.6. Рассмотрим задачу сортировки п целых чисел из интервала от О до

- 1. Выполним сортировку этих чисел в два этапа. На первом этапе используем п "карманов", индексированных целыми числами от О до и - 1. Поместим каждое сортируемое число i в список "кармана" с номером i mod п. Но в отличие от процедуры листинга 8.12 каждый новый элемент помешается не в начало списка, а в его конец, и это очень важное отличие. Заметим, что если мы хотим эффективно выполнить вставку элементов в конец списков, то надо для представления списков использовать связанные списки, а также указатели на концы списков.

Например, пусть и = 10, а список сортируемых чисел состоит из точных квадратов от 0 до 9, расположенных в случайном порядке 36, 9, О, 25, 1, 49, 64, 16, 81, 4. В этом случае номер "кармана" для числа i равен самой правой цифре в десятичной записи числа i. В табл. 8.5,а показано размещение сортируемых чисел по спискам "карманов". Отметим, что числа появляются в списках в том же порядке, в каком они расположены в исходном списке, например в списке "кармана" 6 будут располагаться числа 36, 16, а не 16, 36, поскольку в исходном списке число 36 предшествует числу 16.

Так как по ранее сделанным предположениям значения ключей имеют перечислимый тип данных, а в языке Pascal всегда можно объявить собственный перечислимый тип, то в данном случае можно объявить тип данных, содержащий все значения ключей. После этого программа из листинга 8.12 будет выполняться за время 0(п + т). Но такой подход имеет очевидные недостатки: во-первых, надо перечислить все значения ключей (если их несколько сотен, то это может породить определенные проблемы), во-вторых, значения ключей должны быть записаны в возрастающем порядке, т.е. необходимо провести предварительную сортировку ключей, и, в третьих, программа с таким объявлением типа будет работать только на данном множестве ключей. Именно эти соображения приводят к необходимости модификации алгоритма "карманной" сортировки. - Прим. ред.



Теперь содерясимое "карманов" поочередно объединим в один список:

О, 1, 81, 64, 4, 25, 36, 16, 9, 49. (8.10)

Если в качестве структуры данных мы использовали связанные списки, а также указатели на концы списков, то операция конкатенации п элементов, содержащихся в карманах, займет время порядка 0(п).

Целые числа из списка, созданного путем конкатенации на предьщущем этапе, снова распределяются по карманам, но рке по другому принципу. Теперь число i помещается в карман с номером [i/n], т.е. номер кармана равен наибольшему целому числу, равному или меньшему i/n (другими словами, квадратные скобки здесь и далее в этой главе обозначают операцию взятия целой части числа). На этом этапе добавляемые в "карманы" числа также вставляются в концы списков. После распределения списков по "карманам" снова выполняется операция конкатенации всех списков в один список. В результате получим отсортированный список элементов.

В табл. 8.21,6 показан список (8.10), распределенный по "карманам", в соответствии с правилом, когда число i вставляется в "карман" с номером [i/n].

Таблица!

В.5. Двухэтапная „карманная сортировка

"Карман"

Содерлшмое

"Карман"

Содерлшмое

0, 1,4, 9

1, 81

64, 4

36, 16

9, 49

Чтобы увидеть, почему этот алгоритм работает правильно, достаточно заметить, что когда числа помешаются в один "карман", например числа О, 1, 4 и 9 - в карман О, то они будут располагаться в возрастающем порядке, поскольку в списке (8.10) они упорядочены по самой правой цифре. Следовательно, в любом "кармане" числа также будут упорядочены по самой правой цифре. И, конечно, распределение чисел на втором этапе по "карманам" в соответствии с первой цифрой гарантирует, что в конечном объединенном списке все числа будут расставлены в возрастающем порядке.

Покажем правильность работы описанного алгоритма в обшем случае, предполагая, что сортируемые числа являются произвольными двузначными целыми числами из интервала от О до - 1. Рассмотрим целые числа i = an + Ь я J = сп + d, где все числа а, Ь, с я d из интервала от 1 до и - 1. Пусть i <j. Тогда неравенство а > с невозможно, поэтому а < с. Если а < с, тогда на втором этапе сортировки число i будет находиться в "кармане" с меньшим номером, чем номер "кармана", в котором находится число j, и, следовательно, в конечном списке число i будет предшествовать числу j. Если а = с, то число Ь должно быть меньше, чем d. Тогда в объединенном списке после первого этапа сортировки число i будет предшествовать числу j, поскольку число i находилось в "кармане" с номером Ь, а число j - ъ кармане с номе-





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.0021