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

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

3.2. ЦИФРОВАЯ СОРТИРОВКА

Начнем с последовательности целых чисел а,, Oi, ... , а„, заключенных между О и т-1. Если т не слишком велико, ее можно упорядочить следующим образом.

1. Организуем т пустых очередей по одной для каждого целого числа от О до т-1. Каждую такую очередь назовем черпаком.

2. Просмотрим последовательность ai, Дз. • • • , а„ слева направо, помещая элемент at в очередь с номером а,.

3. Сцепим эти очереди (содержимое (1+1)-й очереди приписывается к концу 1-й очереди) и получим в результате упорядоченную последовательность.

Так как любой элемент можно вставить в i-ю очередь за постоянное время, то п элементов можно вставить в очереди за время 0{п). Конкатенация (сцепление) т очередей требует времени 0(т). Если т есть 0{п), то этот алгоритм сортирует п целых чисел за время 0(п). Назовем его сортировкой вычерпыванием.

Процедуру сортировки вычерпыванием можно обобщить так, чтобы она упорядочивала последовательность кортежей (т. е. списков) целых чисел в лексикографическом порядке. Пусть - линейный порядок на множестве S. Лексикографическим порядком называется такое продолжение отношения на кортежи элементов из S, при котором (si, Sa, . . . , Sp){ti, ti, . . . , t) означает, что выполнено одно из условий:

1) существует такое целое число /, что Sj<Ztj и для всех /<:/ справедливо 5=/,

2) р<(7 и Si = ti при l<t<p.

Например, в словаре слова расположены в лексикографическом порядке, если рассматривать их как кортежи из букв (на буквах задан естественный алфавитный порядок).

Сначала обобщим сортировку вычерпыванием на последовательности, состоящие из Л-членных кортежей, компонентами которых



ЯВЛЯЮТСЯ целые числа от О до т-1. Сортировка осуществляется с помощью k прохождений по данной последовательности, на каждом из которых применяется сортировка вычерпыванием. Во время первого прохождения кортежи упорядочиваются по их k-ы компонентам. Во время второго прохождения полученная последовательность упорядочивается по {k-1)-м компонентам. При третьем последовательность, полученная после второго прохождения, упорядочивается по (k-2)-м компонентам.и т. д. При к-и (последнем) прохождении последовательность, полученная после (к.-1)-го прохождения, упорядочивается по первым компонентам ).

Теперь элементы последовательности расположены в лексикографическом порядке.

Дадим точное описание этого алгоритма.

Алгоритм 3.1. Лексикографическая сортировка

Вход. Последовательность Л, ... , Л„, где Л г есть Л-член-ный кортеж (оа. ац, , ащ), в котором Щ] - целое число между О и т-1. (Удобной структурой данных для этой последовательности кортежей является массив размера nxk.)

Выход. Последовательность Ви В2, ... , В„, представляющая

собой такую перестановку Ai, А......Л„, что BiBi+i при 1:

<г<п.

Метод. Чтобы поместить Л-членный кортеж Л j в некоторый черпак, в действительности надо сдвинуть лишь указатель на At. Поэтому кортеж Л; можно добавить в черпак за фиксированное время, а не только за время, ограниченное числом k. Для хранения "текущей" последовательности элементов применяется очередь, называемая ОЧЕРЕДЬ. Используется также массив Q, состоящий из т черпаков, в котором черпак Q[i] предназначен для хранения тех Л-членных кортежей, у которых число i стоит в компоненте, рассматриваемой в данный момент. Алгоритм приведен на рис. 3.1. □

Теорема 3.1. Алгоритм 3.1 лексикографически упорядочивает последовательность, состоящую из п k-чденных кортежей, каокдая компонента которых является целым числом меокду О и т-1, за время 0({m+n)k).

Доказательство. Доказательство корректности алгоритма 3.1 проводится индукцией по числу выполнений внешнего цикла. Предположение индукции таково: после г выполнений этого цикла кортежи в ОЧЕРЕДИ будут расположены в лексикографическом порядке по их г последним компонентам. Требуемый результат

1) Во многих практических ситуациях достаточно применить сортировку вычерпыванием только по нескольким первым компонентам. Если число элементов, попавших в каждый черпак, мало, можно упорядочить слова в каждом черпаке с помощью какого-нибудь прямолинейного алгоритма сортировки, такого, как сортировка взбалтыванием.



begin

поместить Aj, Л, .... Л„ в ОЧЕРЕДЬ; for / -/е step -1 until 1 do begin

for I*-0 until m-1 do сделать Q[l] пустым; while список ОЧЕРЕДЬ не пуст do begin

пусть Ai - первый элемент в списке ОЧЕРЕДЬ; переместить Л,- из списка ОЧЕРЕДЬ в черпак Qffl,/] end;

for / - О until m-1 do

присоединить содержимое Q[l] к концу списка ОЧЕРЕДЬ

Рис. 3.1. Алгоритм лексикографической сортировки.

легко получить, если заметить, что (г+1)-е выполнение внешнего цикла упорядочивает множество кортежей по их (г+1)-й с конца компоненте, а в ситуации, когда два кортежа оказались в одном и том же черпаке, первый из них предшествует второму в лексикографическом порядке, определяемом г последними компонентами.

Одно выполнение внешнего цикла алгоритма 3.1 занимает время 0{т+п). Цикл повторяется k раз, и это дает временную сложность ОЦт+п)к). □

Алгоритм 3.1 находит разнообразные приложения. Долгое время он применялся в машинах, сортирующих перфокарты. С его помощью можно также упорядочить множество из 0(п) целых чисел, лежащих между О и п*-1, за время 0(kn), так как любое такое число можно считать й-членным кортежем цифр от О до п-1 (т. е. представленным в системе счисления с основанием п).

Нашим последним обобщением сортировки вычерпыванием будет распространение ее на кортежи неодинаковой длины, которые мы будем называть цепочками. Если самая длинная цепочка имеет длину k, то можно каждую цепочку дополнить специальным символом до длины k и затем применить алгоритм 3.1. Однако, если длинных цепочек мало, такой подход по двум причинам приведет к неоправданной неэффективности. Во-первых, при каждом прохождении просматривается каждая цепочка; во-вторых, каждый черпак Q[i] анализируется даже в том случае, когда почти все черпаки пу-

4 А. Ахо, Дж. Хопкрофт, Дж. Ульман 91





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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021