1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 19
Текст из файла (страница 19)
Алгоритм 3.1. Лекснкографическая сортировка Вход. Последовательность А„ А„ ..., А„, где Аг есть й-членный кортеж (аеь а~„..., аох), в котором ໠— целое число между О и т — 1. (Удобной структурой данных для этой последовательности кортежей является массив размера пхй.) Выход.
Последовательность „„..., В„, представляющая собой такую перестановку А„А„..., А„, что Вг(Вьет прн 1~ (1(п. Метод. Чтобы поместить й-членный кортеж Аг в некоторый черпак, в действительности надо сдвинуть лишь указатель на А,. Поэтому кортеж А, можно добавить в черпак за фиксированное время, а не только за время, ограниченное числом й. Для хранения "текущей" последовательности элементов применяется очередь, называемая ОЧЕРЕДЬ.
Используется также массив (), состоящий из т черпаков, в котором черпак ®1 предназначен для хранения тех к-членных кортежей, у которых число 1 стоит в компоненте, рассматриваемой в данный момент. Алгоритм приведен на рис. 3.1. ( ) Теорема 3.1. Алгоритм 3.1 лексикографически упорядочивает последовательность, состоим(ую из п й-членных кортежем, каждая компонента которых явлтется г(елым числом между О и т — 1, за время 0((т+п)й).
Д о к а з а т е л ь с т в о. Доказательство корректности алгоритма 3.1 проводится индукцией по числу выполнений внешнего цикла. Предположение индукции таково: после г выполнений этого цикла кортежи в ОЧЕРЕДИ будут расположены в лексикографическом порядке по их г последним компонентам. Требуемый результат ') Во многих практических снтуапиях достаточно применить сортировку вычерпыванием только по нескольким первым компонентам. Если число алемеатов, попавших в каждый черпак, мало, можно упорядочить слова в каждом черпаке с помощью какого-нибудь прямолинейного алгоритма сортировки, такого, как сортировка набалтыванием. Фь 3.2. циФРОВАя сОРтиРОВкА Ьеи!п поместить А„А„..., А„в ОЧЕРЕДЬ; 1ог ! — й з!ер — 1 ппШ 1 до Ьед(п !ог ! — О ап!!1 и — 1 до сделать Д[!) пустым; вЬ11е список ОЧЕРЕДЬ не пуст бо Ьеи1п пусть А,— первый элемент в списке ОЧЕРЕДЬ; переместить А; из списка ОЧЕРЕДЬ в черпак Яа,~) еаза; !Ог ! — О пп!П и — 1 бо присоединить содержимое Щ к концу списка ОЧЕРЕДЬ епт! еаза Рис.
ЗЛ. Алгоритм лексикографической сортировки. легко получить, если заметить, что (г+1)-е выполнение внешнего цикла упорядочивает множество кортежей по их (г+1)-й с конца компоненте, а в ситуации, когда два кортежа оказались в одном и том же черпаке, первый из них предшествует второму в лексико- графическом порядке, определяемом г последними компонентами. Одно выполнение внешнего цикла алгоритма 3.1 занимает время 0(От+и).
Цикл повторяется й раз, и это дает временную сложность 0((гп+п)й). () Алгоритм 3.1 находит разнообразные приложения. Долгое время он применялся в машинах, сортирующих перфокарты. С его помощью можно также упорядочить множество из 0(л) целых чисел, лежащих между О и пл — 1, за время 0(йп), так как любое такое число можно считать й-членным кортежем цифр от О до п — 1 (т. е. представленным в системе счисления с основанием л). Нашим последним обобщением сортировки вычерпыванием будет распространение ее на кортежи неодинаковой длины, которые мы будем называть цепочками.
Если самая длинная цепочка имеет длину й, то можно каждую цепочку дополнить специальным символом до длины й и затем применить алгоритм 3.1. Однако, если длинных цепочек мало, такой подход по двум причинам приведет к неоправданной неэффективности. Во-первых, при каждом прохождении просматривается каждая цепочка; во-вторых, каждый черпак !4!!! анализируется даже в том случае, когда почти все черпаки пу- 4 А. Ако, Дж. ХавкрсФт. Дж. Ульмаи ГЛ. 3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ сты. Мы дадим алгоритм, сортирующий и-элементную последовательность цепочек различной длины, компонентами (т. е. буквами) которых служат числа между О и т — 1; время работы этого алгоритма на такой последовательности равно 0(т+1"), где 1, — длина Ьй цепочки, а 1Р =я~~ 1П Этот алгоритм полезен в ситуации, когда числа и и 1е имеют одинаковый порядок 0(п).
Суть этого алгоритма в том, что сначала он располагает цепочки в порядке убывания длин. Пусть 1,„— длина самой длинной цепочки. Тогда, как и в алгоритме 3.1, сортировка вычерпыванием применяется 1,„раз. Но первое такое применение (по самой правой компоненте) сортирует лишь цепочки длины 1 ОР Второе применение сортирует (в соответствии с (1 „„— 1)-й компонентой) те цепочки, длина которых не менее 1,„— 1, и т. д.
Например, пусть нужно упорядочить последовательность из трех цепочек: ЬаЬ, аЬЕ и а. (Мы условились считать компонентами кортежей целые числа, но для удобства записи мы часто будем использовать буквы. Это не вызывает трудностей, потому что всегда, когда мы пожелаем, можно заменить а, Ь и с на О, 1 и 2.) В этом примере 1,„=3, так что при первом прохождении последовательности сортируются только первые две цепочки по третьей компоненте. При этом ЬаЬ помещается в Ь-черпак, а аЬС вЂ” в с-черпак; а-черпак остается пустым. При втором прохождении эти же две цепочки сортируются по второй компоненте, Теперь а-черпак и Ь-черпак становятся занятыми, а с-черпак пустым.
При третьем (последнем) прохождении сортируются все три цепочки по первой компоненте. На этот раз а- и Ь-черпаки оказываются занятыми, а с-черпак пустым. Заметим, что в общем случае при данном прохождении могут оказаться пустыми много черпаков. Поэтому полезен предварительный шаг, определяющий, какие черпаки будут при данном прохождении непустыми. Список непустых черпаков для каждого прохождения формируется в порядке возрастания номеров черпаков. Это позволяет сцепить непустые черпаки за время, пропорциональное их числу, Алгоритм 3.2. Лекснкографическая сортировка цепочек разной дли- ны Вход. Последовательность цепочек (кортежей) А „А „ ..., А„, компоненты которых представлены целыми числами от О до т — 1.
Пусть 1, — длина цепочки А,=(а;„аы,..., аи,.) и1,„— наибольшее из чисел 1П Выход. Перестановка В„ В„ ..., В„ цепочек Аи такая, что В,<В,<...~~В„. З.е. ЦИФРОВАЯ СОРТИРОВКА Метод. 1. Начнем с формирования списков (по одному для каждого 1, 1<1(1,„) тех символов, которые появляются в 1-й компоненте одной или более цепочек. Для этого сначала построим пары (1, ап) для каждой компоненты ап каждой пепочки А» !(1(л, 1(1(1!.
Такая пара указывает, что в 1-й компоненте некоторой цепочки стоит число аг, Множество этих пар лексикографически упорядочивается с помощью очевидного обобщения алгоритма 3.! '). Затем, просматривая упорядоченный так список слева направо, формируем упорядоченные списки НЕПУСТОЙИ для 1(К1,„, такие, что НЕПУСТОЙИ содержит точно те символы, которые появляются в 1-й компоненте некоторой цепочки. Иными словами, НЕПУСТОЙИ содержит в упорядоченном виде все целые числа ), для которых аг,— — 1 при некотором !.
2. Определяем длину каждой цепочки. Затем формируем списки ДЛИНАИ для 1(1(1,„, такие, что ДЛИНАИ содержит все цепочки длины 1. (Хотя речь все время идет о перемещении цепочек, фактически мы передвигаем только указатели на них. Поэтому каждую цепочку можно добавить в список ДЛИНАИ за фиксированное число шагов.) 3. Теперь сортируются цепочки по компонентам, как в алгоритме 3.1, начиная с компонент с номером 1,„, Однако после г-го прохождения цепочек ОЧЕРЕДЬ содержит только те из них, длина которых не менее 1,„— г+1, и они уже будут расположены в соответствии с компонентами, имеющими номера от 1,„— г+1 до 1,„. Списки типа НЕПУСТОЙ, сформированные на шаге 1, помогают определить при каждом применении сортировки вычерпыванием занятые черпаки.
Эта информация используется для того, чтобы ускорить сцепление черпаков. Соответствукнцая часть алгоритма на Упрощенном Алголе приведена на рис. 3.2. Пример 3.1. Упорядочим последовательность цепочек а, ЬаЬ н аЬс с помощью алгоритма 3.2. Одно из возможных представлений этих цепочек — структура данных, изображенная на рис. 3.3.
ЦЕПОЧКА — зто такой массив, что ЦЕПОЧКАИ вЂ” указатель на представление г-й цепочки, у которой длина и компоненты хранятся в массиве ДАННЫЕ. Клетка в массиве ДАННЪ|Е, куда указывает указатель из элемента ЦЕПОЧКА(1!, дает число| символов в г-й цепочке. Следующие 1 клеток массива ДАННЫЕ содержат эти символы. Списки цепочек, используемые алгоритмом 3.2, в действительности являются списками указателей того же типа, что и в массиве ЦЕПОЧКА.
В остальной части этого примера мы будем для удоб- ') В алгоритме 3.1 было сделано допущение, что все компоненты выбираются нз одного и того же алфавита. Здесь же вторая компонента принимает аначення от О до гп †!. а первая — от ! до !м,„. гл. з. соотировкл и пооядковын статистики Ьсй1п 1. сделать список ОЧЕРЕДЬ пустым; 2. 1ог 1 — О пп(11 т — 1 мо сделать Щ пустым; 3. аког 1 — 1, айер — 1 пп(11 1 до Ьед(п 4. присоединить содержимое списка ДЛИНА[11 к началу списка ОЧЕРЕДЬ '); 5. тнЬ11е список ОЧЕРЕДЬ не пуст до Ьеп(п 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
