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

сты. Мы дадим алгоритм, сортирующий п-элементную последовательность цепочек различной длины, компонентами (т. е. буквами) которых служат числа между О и т-1; время работы этого алгоритма на такой последовательности равно 0{т+1*), где It - длина

£-й цепочки, а /*=2 h- Этот алгоритм полезен в ситуации, когда числа m и /* имеют одинаковый порядок 0(п).

Суть этого алгоритма в том, что сначала он располагает цепочки в порядке убывания длин. Пусть 1 - длина самой длинной цепочки. Тогда, как и в алгоритме 3.1, сортировка вычерпыванием применяется /„ах раз. Но первое такое применение (по самой правой компоненте) сортирует лишь цепочки длины /„ах- Второе применение сортирует (в соответствии с (/„ах-Ой компонентой) те цепочки, длина которых не менее /„ах-1. и т. д.

Например, пусть нужно упорядочить последовательность из трех цепочек: bob, abc и а. (Мы условились считать компонентами кортежей целые числа, но для удобства записи мы часто будем использовать буквы. Это не вызывает трудностей, потому что всегда, когда мы пожелаем, можно заменить а, ft и с на О, 1 и 2.) В этом примере /тах=3, так что при первом прохождении последовательности сортируются только первые две цепочки по третьей компоненте. При этом bab помещается в й-черпак, а abc - в с-черпак; а-чер-пак остается пустым. При втором прохождении эти же две цепочки сортируются по второй компоненте. Теперь а-черпак и й-черпак становятся занятыми, а с-черпак пустым. При третьем (последнем) прохождении сортируются все три цепочки по первой компоненте. На этот раз а- и й-черпаки оказываются занятыми, а с-черпак пустым.

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

Алгоритм 3.2. Лексикографическая сортировка цепочек разной длины

Вход. Последовательность цепочек (кортежей) Аи Л а, ... Л„, компоненты которых представлены целыми числами от О до

т-1. Пусть /г - длина цепочки Ai=(an, а,......аи.) к 1 -

наибольшее из чисел /,-.

Выход. Перестановка Bi, В.....В„ цепочек Л{, такая, что



Метод.

1. Начнем с формирования списков (по одному для каждого /,

тех символов, которые появляются в 1-й компоненте одной или более цепочек. Для этого сначала построим пары (/, а,-,) для каждой компоненты Оц каждой цепочки Ai, I<i<n, Такая

пара указывает, что в /-Й компоненте некоторой цепочки стоит число йц. Множество этих пар лексикографически упорядочивается с помощью очевидного обобщения алгоритма 3.1 Затем, просматривая упорядоченный так список слева направо, формируем упорядоченные списки НЕПУСТОЙ[/] для такие, что НЕПУ-СТОЙ[/] содержит точно те символы, которые появляются в 1-й компоненте некоторой цепочки. Иными словами, НЕПУСТОЙ[Л содержит в упорядоченном виде все целые числа /, для которых ац=} при некотором i.

2. Определяем длину каждой цепочки. Затем формируем списки ДЛИНА[/] для 1</</шах. такие, что ДЛИНА[/] содержит все цепочки длины /. (Хотя речь все время идет о перемещении цепочек, фактически мы передвигаем только указатели на них. Поэтому каждую цепочку можно добавить в список ДЛИНА!/] за фиксированное число шагов.)

3. Теперь сортируются цепочки по компонентам, как в алгоритме 3.1, начиная с компонент с номером Однако после i-ro прохождения цепочек ОЧЕРЕДЬ содержит только те из них, длина которых не менее lnx-+ < и они уже будут расположены в соответствии с компонентами, имеющими номера от /„ах-До тах-Списки типа НЕПУСТОЙ, сформированные на шаге 1, помогают определить при каждом применении сортировки вычерпыванием занятые черпаки. Эта информация используется для того, чтобы ускорить сцепление черпаков. Соответствующая часть алгоритма на Упрощенном Алголе приведена на рис. 3.2. □

Пример 3.1. Упорядочим последовательность цепочек а, bab и аЬс с помощью алгоритма 3.2. Одно из возможных представлений этих цепочек - структура данных, изображенная на рис. 3.3. ЦЕПОЧКА - это такой массив, что ЦЕПОЧКА[/] - указатель на представление t-й цепочки, у которой длина и компоненты хранятся в массиве ДАННЫЕ. Клетка в массиве ДАННЫЕ, куда указывает указатель из элемента ЦЕПОЧКА[г], дает число / символов в 1-й цепочке. Следующие / клеток массива ДАННЫЕ содержат эти символы.

Списки цепочек, используемые алгоритмом 3.2, в действительности являются списками указателей того же типа, что и в массиве ЦЕПОЧКА. В остальной части этого примера мы будем для удоб-

1) В алгоритме 3.1 было сделано допущение, что все компоненты выбираются из одного и того же алфавита. Здесь же вторая компонента принимает значения от О до /п-1, а первая - от 1 до /щах-

4* 99



begin

1. сделать список ОЧЕРЕДЬ пустым;

2. for /*-О until m-1 do сделать Q[j] пустым;

3. for /шах step -1 until 1 do

begin

4. присоединить содержимое списка ДЛИНА[/] к началу

списка ОЧЕРЕДЬ»);

5. while список ОЧЕРЕДЬ не пуст do

begin

6. пусть л,.-первая цепочка в списке ОЧЕРЕДЬ;

7. переместить Л/ из списка ОЧЕРЕДЬ в черпак

end;

8. for / е НЕПУСТОЙ[/] do

begin

9. присоединить содержимое списка Q[j] к концу

списка ОЧЕРЕДЬ; 10. сделать список Q[j] пустым

1) С формальной точки зрения можно присоединять лишь к концу очереди, но конкатенация к началу не должна вызывать никаких трудностей. Более эффективным приемом здесь был бы такой: выбрать цепочки А{ из списка ДЛИНА[/] сначала в строке 6, а затем из списка ОЧЕРЕДЬ и совсем не устраивать конкатенации списков ДЛИНА[/] и ОЧЕРЕДЬ.

Рис. 3.2. Лексикографическая сортировка цепочек разной длины.

ства писать в списках сами цепочки, а не указатели на них. Однако надо помнить, что в очередях хранятся эти указатели, а не сами цепочки.

В части 1 алгоритма 3.2 формируется пара (1, а) из первой цепочки, пары (1, Ь), (2, а), (3, Ь) из второй и (1, а), (2, Ь), (3, с) из третьей. Упорядоченный список этих пар выглядит так: (1, а)(1, а)(1, Ь)(2, а) (2, 6) (3, Ь)(3, с) Просматривая его слева направо, заключаем, что НЕПУСТОЙ [1] = а, Ь; НЕПУСТОЙ [2] = а, Ь; НЕПУСТОЙ Г3 = ft. с





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