СОДЕРЖАНИЕ ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ .............................4 1. Методы вставки. Алгоритм простых вставок. .............4 1.1. Бинарные вставки ...................................5 1.2. Двухпутевые вставки ................................6 1.3. Вставки одновременно нескольких элементов. ............6 1.4. Вставки с убывающим шагом (метод Шелла) .............7 1.5. Вставки в связанный список .............9 1.6. Вставки в несколько связанных списков ............10 2. Обменная сортировка ...................................12 2.1. Метод пузырька ...................................12 2.2. Модификация метода пузырька .......................13 2.3. Быстрая сортировка. ...........................14 2.4. Обменная поразрядная сортировка ......................17 2.5. Параллельная сортировка Бэтчера ......................20 3. Сортировка посредством выбора .........................24 3.1. Использование связанного списка для хранения информации о промежуточных максимумах. ...............24 3.2. Пирамидальная сортировка. ..........................26 4. Сортировка посредством слияния ......................31 4.1. Естественное двухпутевое слияние .....................31 4.2. Простое двухпутевое слияние. .........................34 4.3. Слияние связанных списков ...........................36 5. Распределяющая сортировка .............................38 ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА ..............................42 6. Последовательный поиск ..............................42 6.1. Последовательный поиск в неупорядоченном файле........42 6.2. Последовательный поиск по связанному списку ........43 6.3. Последовательный поиск в упорядоченном файле .....44 6.4. Бинарный поиск в упорядоченном файле. ...............44 6.5. Однородный бинарный поиск ....................45 6.6. Интерполяционный поиск ....................46 7. Поиск по бинарным деревьям .......................47 7.1. Поиск по бинарному дереву. .......................47 7.2. Удаление из бинарного дерева .......................48 7.3. Построение оптимальных бинарных деревьев поиска ......48 7.4. Цифровой поиск по дереву .........................52 7.5. Цифровой поиск для длинных ключей, хранимых в текстовом массиве (Патриция) .......................52 Обозначения, использованные в данном пособии. log логарифм по основанию 2 + + | А | наименьшее целое значение, большее или равное А | А | наибольшее целое значение, меньшее или равное А + + ЛИТЕРАТУРА 1. Д.Кнут,Искусство программирования, М.:Мир,1978. 2. Рейнгольд, Нивергельт, Део, Комбинаторные алгоритмы. Теория и практика, М.:Мир, 1982. ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ 1. Методы вставки. Алгоритм простых вставок. Ниже описан основной алгоритм простых вставок, который порождает несколько модификаций, используемых в заданиях. Алгоритм использует прием, которым пользуются игроки в карты при сортировке только что розданной колоды: очередная карта вставляется между уже упорядочен- ными ранее. Описание алгоритма простых вставок. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информацион- ную часть и ключи, по которым производится упорядочение по возраста- нию. Поскольку информационная часть почти не влияет на процесс сор- тировки, будем предполагать, что файлы, используемые в примерах, состот только из элементов-ключей, а информационная часть записи от- сутствует. Здесь k[1], k[2], ... , k[N] - ключи, по которым производится упорядочение файла. X,i,j - рабочие переменные. +-------- for j=2 to N -----------+ | i=j-1; | | X=k[j]; | |+-----while (X< k[i]) & (i>0)--+ | || k[i+1]=k[i]; | | || i=i-1; | | |+------------------------------+ | | k[i+1]=X; | +---------------------------------+ Для примера возьмем файл, состоящий из 8 элементов: Исх.файл.: 503 87 512 61 908 170 897 275 Алгоритм будет преобразовывать его следующим образом: j=2. Исх : 503 87 X=87 Рез : ш87 503 j=3 : 87 503 ш512 X=512 j=4 : ш61 87 503 512 X=61 j=5 : 61 87 503 512 ш908 X=908 j=6 : 61 87 ш170 503 512 908 X=170 j=7 : 61 87 170 503 512 ш897 908 X=897 j=8 : 61 87 170 ш275 503 512 897 908 X=275 Время работы алгоритма t примерно оценивается формулой: t=a*Nэ+ b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. Модификации алгоритма простых вставок. 1.1. Бинарные вставки Для ускорения числа сравнений при поиске места, в которое нужно вставить элемент X, можно использовать логарифмический поиск. Это означает, что сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д. . При этом число сравнений для каждого j равно примерно log(j). Число пересылок эле- ментов при этом не изменяется и остается примерно равным Nэ/4. Схема алгоритма бинарных вставок может быть получена небольшой модификацией схемы из раздела 6.4. Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N + c*N*logN где a,b,c - неизвестные константы, зависящие от программной реализа- ции алгоритма. 1.2. Двухпутевые вставки Число пересылок можно сократить примерно в 2 раза до Nэ/8, если допустить сдвиги элементов не только вправо, но и влево. Для выход- ного файла резервируется место в памяти, равное 2N+1 ,где N - число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдви- гать меньше элементов. Файл из предыдущего примера будет сортиро- ваться следующим образом. Исх.файл.: 503 87 512 61 908 170 897 275 503 нач. состояние ш87 503 Х=87 87 503 ш512 Х=512 ш61 87 503 512 Х=61 61 87 503 512 ш908 Х=908 61 87 ш170 503 512 908 Х=170 61 87 170 503 512 ш897 908 Х=897 61 87 170 ш275 503 512 897 908 Х=275 Из таблицы видно, что присоединение новых элементов к выходному файлу происходит как справа, так и слева от центрального элемента 503 с возможным сдвигом вправо или влево. Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 1.3. Вставки одновременно нескольких элементов. Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, ... Xm, которые имеют значения элементов, подлежащих вставке в уже упорядо- ченную часть файла. Х1, X2, ... Xm упорядочены по возрастанию, поэ- тому сравнивая Xm в цикле по переменной i с элементами упорядоченной части, мы можем гарантировать, что, если очередной элемент k[i] больше Xm, то он больше и остальных элементов. Перенос элементов ис- ходного файла вперед в цикле по i выполняется на m элементов, то есть вместо k[i+1]=k[i] в исходном алгоритме в модифицированном ал- горитме записывается k[i+m]=k[i]. При нахождении k[i] такого, что он меньше Хm, Хm ставится на место k[i+m] и m уменьшается на 1. Далее цикл по i продолжается с новым m. Экономия числа переносов элементов достигается за счет переносов сразу на m элементов. Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N + c*N*logN где a,b,c - неизвестные константы, зависящие от программной реализа- ции алгоритма. 1.4. Вставки с убывающим шагом (метод Шелла) Идея алгоритма состоит в обмене элементов, расположенных не толь- ко рядом, как в алгоритме простых вставок (п.1), но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов. Для примера возьмем файл из 16 элементов. Сначала прос- матриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упо- рядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап - 4-сортировка, на котором эле- менты в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке. Сортировка мо- жет выполняться методом простых вставок (п.1). Следующий этап - 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом простых вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее тру- доемким, чем при сортировке вставками без предварительных "дальних" обменов. Для данного примера результаты представлены в следующей таблице. Исходный файл.На нем выполняется 8-сортировка.Пары для возможного обмена соединены одинарными или двойными линиями .Двойными линиями обозначены пары, в которых произошел обмен. 503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 +--+---+--+--+----+---+---+---+ | | | | | | | +---+--+--+----+---+---+-------+ | | | | | | +--+--+----+---+---+-----------+ | | | | | +--+----+---+---+---------------+ | | | | +----+---+---+-------------------+ | | | +---+---+-----------------------+ | | +---+---------------------------+ | +-------------------------------+ Файл после 8-сортировки. Линиями соединены четверки для следующе- го этапа. 503 87 154 61 612 170 765 275 653 426 512 509 908 677 897 703 +---+--+--+---+---+---+---+---+---+---+---+---+ | | | +--+--+-------+---+---+-------+---+---+-------+ | | +--+-----------+---+-----------+---+-----------+ | +---------------+---------------+---------------+ Файл после 4-сортировки. Линиями соединены восьмерки для следую- щего этапа. 503 87 154 61 612 170 512 275 653 426 765 509 908 677 897 703 +--+---+--+---+---+---+---+---+---+---+---+---+---+---+ | +------+-------+-------+-------+-------+-------+-------+ Файл после 2-сортировки: 154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 Файл после окончательной сортировки (1-сортировки): 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Время работы алгоритма t примерно оценивается формулой: t=a*N**b где a и b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 1.5. Вставки в связанный список Среди общих способов улучшения алгоритма простых вставок можно рассмотреть способ, основанный на изменении структуры данных. Сорти- ровка простыми вставками состоит из двух основных операций: - просмотра исходного файла со сравнением переменной Х с элементами K[i] файла; - вставки нового элемента путем сдвига оставшихся элементов вправо. Файл до сих пор рассматривался как линейный список и для выполне- ния операции вставки в нем необходимо переместить в среднем половину элементов . Известно, что для операций вставки идеально подходит связанный список, так как в этом случае вставка требует всего лишь изменения нескольких связей. Операция последовательного просмотра для связанного списка почти так же проста, как и для линейного спис- ка. Поскольку файл всегда просматривается в одном направлении, то достаточно иметь список только с одной связью. С другой стороны свя- занное распределение делает невозможным бинарный поиск, поэтому при- обретая преимущество в выполнении операции вставки, мы теряем по сравнению с бинарным поиском в эффективности операции просмотра и сравнения. Рассмотрим алгоритм простых вставок на связанном вперед списке. Дан файл в виде связанныого списка, каждый элемент которого со- держит кроме ключа K[i] еще и указатель на следующий элемент L[i]. Кроме того есть еще дополнительная переменная L[0], содержащая ука- затель на последний N-й элемент файла. Указатель L[N] равен нулю, что является признаком конца списка элементов. +----+----+ +----+----+ +----+----+ |K[1]|L[1]+-->|K[2]|L[2]+->- ... -->|K[N]|L[N]+-> =0 +----+----+ +----+----+ +--+-+----+ | ++---+ |L[0]| +----+ Упорядоченная часть файла формируется в конце списка и L[0] всегда указывает на начало упорядоченной части, в конце алгоритма - на логичес- кое начало списка. Алгоритм имеет следущий вид: for j=N-1 to 1 +--------------------------------+ q +->- p | p=L[0]; q=0; X=K[j]; | +----+ | +----+ | | |L[q]+->-+ |L[p]+->- | + while(p>0 & X>K[p]) ----+ | +----| +----| | +-------------------------| | |K[q]| |K[p]| | | продвижение по списку | | +----+ +----+ | +-------------------------| | | | q=p; p=L[p]; | | | +-------------------------+ | | +------------------------+ | | |вставка | | | +------------------------| | | | L[q]=j; L[j]=p; | | | +------------------------+ | +--------------------------------+ Переменные p и q служат указателями на текущий элемент, причем p=l[q] (q всегда на один шаг отстает от p). Если p=0, то Х - наи- больший элемент и должен попасть в конец списка. Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 1.6. Вставки в несколько связанных списков Идея метода основывается на предположении, что ключи в исходном файле имеют значения в некотором известном диапазоне MAX и в этом диапазоне они распределены довольно равномерно. Тогда по аналогии с методом вставки в один связанный список можно организовать несколь- ко, например, Q списков. Величина Q зависит от ожидаемого среднего количества элементов M в каждом списке то есть Q=N/M, N - количество ключей. При разработке программы нужно проанализировать зависимость времени работы метода от параметра М для различных исходных файлов и дать рекомендации по выбору оптимального значения. Схема алгоритма имеет следующий вид. Через Q обозначено коли- чество списков, массив B[1]...B[Q] служит для хранения указателей на начала отдельных списков. Перед началом работы алгоритма элементы массива В предполагаются равными 0.Каждый i-й элемент исходного фай- ла содержит ключ K[i] и указатель L[i] на следующий элемент списка. Значение L[i]=0 соответствует последнему элементу в списке, указатель B[1] указывает на начало первого подсписка и одновременно на начало всего списка. Через minK обозначено минимальное значение ключа в файле, через М - среднее выбранное значение количества эле- ментов в подсписке. d - номер текущего списка, в который должен быть вставлен элемент K[j]. Величина R=MAX/Q есть диапазон значений клю- чей, приходящийся на один список. for j=N-1 to 1 +--------------------------------------------+ | X=K[j]; d= (X-minK)/R+1;(деление нацело)| | p=B[d]; | | q=0; | | | | +-while(p>0 & X>K[p]) ----------+ | | | | | | | продвижение по списку | | | +--------------------------------| | | | q=p; | | | | p=L[p]; | | | +--------------------------------+ | | +--------------------------------+ | | |Вставка элемента Х | | | +--------------------------------| | | | if(q=0) B[d]=j; else L[q]=j; | | | | L[j]=p; | | | +--------------------------------+ | +--------------------------------------------+ Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2. Обменная сортировка Название этой группы методов произошло от основного типа опера- ций, используемого в алгоритмах - обмен двух элементов в файле свои- ми значениями. Эта операция используется и в других группах, поэтому классификацию нельзя признать вполне строгой, но данное разделение тем не менее является традиционным. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортиров- ки, будем предполагать, что файлы, используемые в примерах, состот только из элементов-ключей, а информационная часть записи отсутству- ет. 2.1. Метод пузырька Алгоритм довольно очевиден. Рассмотрим работу алгоритма на примере файла из 16 элементов: исх. проход 1 проход 4 проход 7 файл | проход 2 | проход 5 | проход 8 | | | проход 3 | | проход 6 | | проход 9 | | | | | | | | | | 703 +->908 908 908 908 908 908 908 908 908 765 | 703 +>897 897 897 897 897 897 897 897 677 | 765 | 703 +>765 703 703 703 703 703 703 612 | 677 | 765--+ 703 765 765 765 765 765 765 509 | 612 | 677 677 677 677 677 677 677 677 154 | 509 | 612 +>653 653 653 653 653 653 653 426 | 154 | 509 | 612 612 612 612 612 612 612 653 | 426 | 154 | 509 +->512 512 512 512 512 512 275 | 653 | 426 | 154 | 509 509 509 509 509 509 897 | 275 | 653--+ 426 | 154 +>503 503 503 503 503 170 | 897--+ 275 +>512-+ 426 | 154 +>426 426 426 426 908-+ 170 +->512--+ 275 +>503-+ 426-+ 154 +>275 275 275 61 +->512-+ 170 503--+ 275 275 275-+ 154 +>170 170 512-+ 61 +->503 170 170 170 170 170-+ 154 154 87 +->503-+ 61 +>87 87 87 87 87 87 87 503-+ 87 87 --+ 61 61 61 61 61 61 61 Пары стоящих рядом элементов просматриваются в направлении снизу вверх и сравниваются. Если верхний элемент оказывается меньше нижнего по рисунку, то они меняются местами. Продолжая этот процесс цикли- чески, мы в конце концов придем к отсортированному файлу.Файл располо- жен вертикально снизу вверх, чтобы эффект всплывающего пузырька вы- глядел более наглядно. Элементы с большим значением ключа "всплывают" наверх, после последовательных сравнивнений с соседними элементами. Алгоритм имеет следующий вид. b=N; while ( b + 0 ) +-------------------------------------------+ | t=0; | | for j=1 to b-1 do | |+----------------------------------------+ | || +---------------+ | | || | | | | через <-> обозначена || if ( k[j] > k[j+1] ) | k[j]<->k[j+1]| | | операция обмена || | t=j; | | | значениями двух || +---------------+ | | переменных |+----------------------------------------+ | | b=t; | +-------------------------------------------+ Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.2.Модификация метода пузырька Модификация метода пузырька состоит в том, что файл можно прос- матривать как с начала до конца, так и с конца до начала поперемен- но. Это несколько сокращает число перемещений элементов. Схема пере- мещений элементов будет в этом случае иметь следующий вид. исх. проход 1 проход 4 проход 7 файл | проход 2 | проход 5 | | | | проход 3 | | проход 6 | | | | | | | | | 703 +->908 908 908 908 908 908 908 765 | 703-+ 765 +->897 897 897 897 897 677 | 765 +->703 | 765 765 765 765 765 612 | 677 677 | 703 703 703 703 703 509 | 612 612 | 677 677 677 677 677 154 | 509 509 | 612 612 +>653 653 653 426 | 154-+ 426 | 509 509 | 612 612 612 653 | 426 | 653 | 426-+ 653-+ 509-+ 512 512 275 | 653 | 275 | 653 +->426 +>512 +>509 509 897 | 275 | 897-+ 275-+ 512-+ 426-+ 503 503 170 | 897 | 170 +->512 +->275 +>503 +>426 426 908-+ 170 | 512-+ 170-+ 503-+ 275 275 275 61 +->512 +->154 +->503 +->170 170 170 170 512-+ 61 -+ 503-+ 154 154 154 154 154 87 +->503 | 87 87 87 87 87 87 503-+ 87 +->61 61 61 61 61 61 Проход 1 осуществлялся с начала в конец, проход 2 - с конца в на- чало, проход 3 снова с начала в конец и т.д. . Как видно из таблицы, этот алгоритм потребовал на 2 прохода меньше, чем исходный. Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.3. Быстрая сортировка. Основная стратегия ускорения алгоритмов сортировка - обмены между как можно более дальними элементами исходного файла - в методе быст- рой сортировки реализована за счет того, что один из ключей в исход- ном файле используется для разделения его на два подфайла так, чтобы слева от выбранного элемента находились только элементы с меньшими ключами, а справа - только с большими. Элемент, разделяющий файл, помещается между его двумя подфайлами и процедура выполняется рекур- сивно для каждой половины до тех пор, пока в очередном новом подфай- ле не окажется меньше, чем М элементов, где М - заранее выбранное число. Рассмотрим схему алгоритма. l=1;r=N; | +>=+======<==========================================================+ | if(r-l < M) +-----------------------------------------------------+| | | | Отсортировать часть файла K[l] ... K[r] простыми || | | | вставками || | | | if (стек пуст) Конец алгоритма. || | | | +---------------------------------+ || | | | else |взять из стека элемент (l',r') +>=++ | | | |l=l' ; r=r' ; | | | | | +---------------------------------+ | | | +---------------------+-------------------------------+ | +>=+=<===========================+ | +---+------+---------+ | |Выбор Х | X=K[l]; | | +----------+---------+ | i=l; j=r; | | | +===========<====+===<======= =>==+========<=======+ | if(X+ if(X>K[i]) i=i+1=>+ | +----------------+ +---------------+ | if(j>i)|K[i]=K[j];i=i+1;+=>= if(j>i) |K[j]=K[i];j=j-1| | +----------------+ ++--------------+ | else K[i]=X =>=+ ==<============+ | | else K[j]=X;i=j;=>+ | | | | +--------+--------------------------------------------+---+ | else | Поместить в стек большую половину файла: либо (l,i-1), | | | либо (i+1,r) и установить для оставшейся половины либо | | | l=i+1, либо r=i-1 соответственно. | | +---------------------------------------+-----------------+ +=================================<================+ Сортировка подфайлов, содержащих меньше чем М элементов, выполня- ется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части. Блок выбора Х в простейшем случае формулируется как X=K[l], одна- ко это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l] ... K[r] и обменять его с K[l]. Ниже быстрая сортировка проиллюстрирована примером файла из 16 элементов. Квадратными скобками [] выделены подфайлы, подлежащие последующей сортировке. В рамку взяты элементы, принятые на данном шаге за Х. M принято за 1 - наименьшее возможное значение, то есть в данном случае алгоритм не переходит к другому методу для коротких отрезков, меньших M. Для первого шага показаны направления пересылки в соответсвии со схемой алгоритма. Числа на линиях определяют поря- док, в котором выполняются пересылки. N | шага| Состояние файла ----+----------------------------------------------------------------- | +--<-5-------+ | |+->-4-------+------+ | +--<-3-++-----------+------++ | |+->-2-++-----------+------++---+ | +-<-1--++-----++-----------+------++--+| | +-+-+ || || +>-6+| || || исх.| |503| 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 | +---+ |+ +---+ + + + 1 || |154| 87 426 61 275 170|503|897 653 908 512 509 612 677 765 703| |+ +---+ + + + |+ +--+ + + + + + 2 || |61| 87|154|426 275 170|503|897 653 908 512 509 612 677 765 703| |+ +--+ + + + + + | + +---+ + + + 3 | 61 87 154| |426| 275 170|503|897 653 908 512 509 612 677 765 703| | + +---+ + + + | + +---+ + + + 4 | 61 87 154| |170| 275|426 503|897 653 908 512 509 612 677 765 703| | + +---+ + + + | + +---+ + 5 | 61 87 154 170 275 426 503| |897| 653 908 512 509 612 677 765 703| | + +---+ + | + +---+ + 6 | 61 87 154 170 275 426 503| |703| 653 765 512 509 612 677| 897 908 | + +---+ + | + +---+ + 7 | 61 87 154 170 275 426 503| |677| 653 612 512 509 | 703 765 897 908 | + +---+ + | + +---+ + 8 | 61 87 154 170 275 426 503| |509| 653 612 512 | 677 703 765 897 908 | + +---+ + | + +---+ + 9 | 61 87 154 170 275 426 503 509| |653| 612 512 | 677 703 765 897 908 | + +---+ + | + +---+ + 10 | 61 87 154 170 275 426 503 509| |512| 612 | 653 677 703 765 897 908 | + +---+ + | 10 | 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 | Время работы алгоритма t примерно оценивается формулой: t=a*N*logN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.4. Обменная поразрядная сортировка Данный метод использует двоичное представление ключей. Файл сор- тируется последовательно по битам двоичного представления ключей, начиная со старшего. Ключи, имеющие значение данного бита, равное нулю, ставятся в левую половину файла, а ключи со значением бита 1 - в правую. Ниже приведена схема алгоритма поразрядной сортировки. Функция b(ключ) возвращает значение ьита с номером b аргумента, m - максимальное количество значащих битов в ключах. l=1; r=N; b=1; | +==>=+==<==============================================+ | | +===========<===========================+===============+ | | +--+-------------------------------------+ | | | | | if(стек пуст) Конец; | | | | if(l=r) | +------------------------------+ | | | | | else |l=r+1; | | | | | | |Взять из стека элемент (r',b')+>=+=+ | | | |r=r'; b=b'; | | | | | +------------------------------+ | | | +----------------------------------------+ | | i=l; j=r; | | +----------------------------------------+ | | +=if(b(K[i])=1)|j=j-1;==========<===========+ | | | | | +------------------+---------+ | | | | |if(i<=j) | if(b(K[j+1])=1) =+ | | | | | | | +---------------+ | | | | | | | else | K[i]<->K[j+1] +>=+ | | | | | | | +---------------+ | | | | | | |else =>+ +-------------------------+--+ | | | | +-------+---------------------------+----+ | | +====<=============+ | | | | +----------+---+---------------------------+------------+ | | else | i=i+1; | | | | | | if(i<=j)=+ | | | | | +-------+-------------------------------------+ | | | | | b=b+1; | | | | | else | if(b>m) =>==================================+==+====+ +====<====+======+==================+=<=+==============<=+ | | | | if(j+ | | | | | | +-------------- +----------------+---+ | | | | else |if(j=l) l=l+1=>+ | | | | | | | +------------------------+ | | | | | | |else | Поместить в стек (r,b);+>+ | | | | | | | r=j; | | | | | | | +------------------------+ | | | | | +------------------------------------+ | | | +---------------------------------------------+ | +-------------------------------------------------------+ Пример использования этого алгоритма приведен ниже. Значения эле- ментов файла даны в 16-ричной системе счисления.Квадратные скобки [] использованы для обозначения подфайлов с одинаковым значением бита b (b=1 соответствует старшему биту ). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |l r b ---------------------------------------------------------------+------- +- -+| |1F7 57 200 3D 38C AA 381 113 28D 1AA 9A 1FD 264 2A5 2FD 2BF|| 1 16 1 | -++- || |1F7 57 1FD 3D 9A AA 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 1 8 2 | -++- || || |AA 57 9A 3D||1FD 1F7 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 1 4 3 | -++- || || || |3D 57||9A AA||1FD 1F7 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 1 2 4 +- -+| || || || | || || || 3D 57 |9A AA||1FD 1F7 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 3 4 4 | || || || 3D 57 |9A AA||1FD 1F7 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 3 4 5 +- -+| || || | || || 3D 57 9A AA|1FD 1F7 1AA 113||28D 381 38C 200 264 2A5 2FD 2BF|| 5 8 3 +- +- || || 3D 57 9A AA 113|1F7 1AA 1FD||28D 381 38C 200 264 2A5 2FD 2BF|| 6 8 4 +- +- || || 3D 57 9A AA 113 1AA|1F7 1FD||28D 381 38C 200 264 2A5 2FD 2BF|| 7 8 5 | || || 3D 57 9A AA 113 1AA|1F7 1FD||28D 381 38C 200 264 2A5 2FD 2BF|| 7 8 6 | || || 3D 57 9A AA 113 1AA|1F7 1FD||28D 381 38C 200 264 2A5 2FD 2BF|| 7 8 7 +- -++- || +- || 3D 57 9A AA 113 1AA 1F7 1FD |28D 381 38C 200 264 2A5 2FD 2BF|| 9 16 2 | -++- || 3D 57 9A AA 113 1AA 1F7 1FD |28D 2BF 2FD 200 264 2A5 ||2FD 381|| 9 14 3 | -++- || || 3D 57 9A AA 113 1AA 1F7 1FD |264 200||2FD 2BF 28D 2A5||2FD 381|| 9 10 4 +- -++- --++- -+| +- -++- -+| 3D 57 9A AA 113 1AA 1F7 1FD 200 264|2A5 2BF 28D 2A5||38C 381||11 14 4 | || || | -++- || || 3D 57 9A AA 113 1AA 1F7 1FD 200 264|28D 2BF 28D||2FD||38C 381||11 13 5 +- || || || +- || || || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D|2BF 2A5||2FD||38C 381||12 13 6 +- -++- -++- || +- || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD |38C 381||15 16 3 | || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD |38C 381||15 16 4 | || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD |38C 381||15 16 5 | || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD |38C 381||15 16 6 | || 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD |38C 381||15 16 7 +- -+| 3D 57 9A AA 113 1AA 1F7 1FD 200 264 28D 2A5 2BF 2FD 38C 381 |17 - - Время работы алгоритма t примерно оценивается формулой: t=a*N*logN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 2.5. Параллельная сортировка Бэтчера Для получения алгоритма обменной сортировки, время работы которо- го меньше, чем Nэ, необходимо выбирать для сравнения и обмена ключи, расположенные возможно дальше друг от друга. Эта идея уже была реа- лизована в алгоритме сортировки Шелла вставок с убывающим шагом, од- нако в данном алгоритме сравнения выполняются по-другому. + + Рассмотрим схему алгоритма. Здесь t= |logN| - наименьшее целое, равное или превышающее logN ( N>=2). Переменная d имеет смысл шага сортировки, то есть сравниваются ключи K[i] и K[i+d]. Через <-> обо- значена операция обмена значений двух переменных. t-1 p = 2 t-1 +=>q = 2 ; r=0; d=p; | | +===<====================================<======+ | for i=0 to N-d-1 таких, что i&p = r; | | +----------------------------------------+ | | |if(K[i+1] > K[i+d+1]) K[i+1]<->K[i+d+1] | | | +----------------------------------------+ | | if(q=p) | | then | else | | +====<====+====>=========================+ | | | | | | p=p/2;(деление нацело) d=q-p; | | if(p<=0) Конец алгоритма; q=q/2; | | else=>+ r=p; | +=======+ +===>==+ На схеме алгоритма через & обозначена операция поразрядного И, то есть выполнение условия i&p = r означает, что в цикле по i нужно вы- бирать только такие значения i, которые в одном разряде, изменяющем- ся в цикле по p (операция p=p/2 имеет смысл сдвига начального значе- ния 1 в разряде t-1), имеют снала значение 0 (поскольку r=0), а за- тем 1 (поскольку r=p). Проиллюстрируем работу алгоритма примером исходного файла из 16 элементов. Линиями соединены сравниваемые на данном шаге ключи. При d=1 происходит фактически слияние упорядоченных подфайлов K[1],K[3],K[5], ... и K[2],K[4],K[6], ... , то есть сортировку Бэт- чера можно назвать также обменной сортировкой со слиянием. | p q r d | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -----------+------------------------------------------------------------- 8 8 0 8 |503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 | +---+--+---+---+--+---+---+---+ | | | | | | | | +--+---+---+--+---+---+-------+ | | | | | | | +---+---+--+---+---+----------+ | | | | | | +---+--+---+---+---------------+ | | | | | +--+---+---+-------------------+ | | | | +---+---+-----------------------+ | | | +---+---------------------------+ | | +-------------------------------+ 4 8 0 4 |503 87 154 61 612 170 765 275 653 426 512 509 908 677 897 703 | +---+--+---+--+ | | | +---+---+---+---+ | | | | +--+---+------+ | | +---+---+-------+ | | | +---+----------+ | +---+-----------+ | | +--------------+ +---------------+ | 4 4 4 4 |503 87 154 61 612 170 765 275 653 426 512 509 908 677 897 703 | +---+---+---+---+ | | | | +---+---+-------+ | | | +---+-----------+ | | +---------------+ 2 8 0 2 |503 87 154 61 612 170 512 275 653 426 765 509 908 677 897 703 | +---+--+ | +---+---+ | +---+---+ | +---+---+ | | +------+ +-------+ +-------+ +-------+ | 2 4 2 6 |154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 | +---+----------+---+---+ | | | | +----------+---+-------+ | | | +---+-------------------+ | | +-----------------------+ | 2 2 2 2 |154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 | +---+--+ | +---+---+ | +---+---+ | | +------+ +-------+ +-------+ | 1 8 0 1 |154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703 | +--+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | 1 4 1 7 |61 154 87 503 170 512 275 612 426 653 509 765 677 897 703 908 | +------+-------+-------+---+ | | | | +-------+-------+-----------+ | | | +-------+-------------------+ | | +---------------------------+ | 1 2 1 3 |61 154 87 503 170 512 275 612 426 653 509 765 677 897 703 908 | +------+---+ | | +---+---+---+ | | | | +-------+---+ | +-------+---+ | | +-----------+ +-----------+ | 1 1 1 1 |61 154 87 275 170 426 503 509 512 653 612 703 677 897 765 908 | +---+ +---+ +---+ +---+ +---+ +---+ +---+ | |61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 | Время работы алгоритма t примерно оценивается формулой: t=a*N*(logN)э где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 3. Сортировка посредством выбора Идея метода довольно проста: найти наибольший элемент файла и поставить его на место N, найти следующий максимум и поставить его на место N-1 и т.д. до 2-го элемента. Схема алгоритма имеет следую- щий вид. +-------for j=N to 2 ---------------+ | | | m=j; X=K[m]; | | | | +-----for i=j-1 to 1------------+ | | | | | | | +-------------+ | | | | if(X =1 |L[2]+>=1 |L[3]+> наибольший |L[4]+> наибольший +----| +----| +----| среди +----| среди ... |K[1]| |K[2]| |K[3]| первых |K[4]| первых +----+ +----+ +----+ двух +----+ трех Тогда после обмена элементов K[j] и K[m] поиск максимума в сле- дующем цикле по j можно осуществлять среди элементов K[L[m]] ... K[j] при начальных значениях X=K[L[m]], m=L[m], т.к. максимум может "обновиться" только за счет элементов, лежащих правее локального ма- ксимума. Таким образом среднее количество просматриваемых при поиске максимума элементов сокращается примерно в два раза. Модифицированный алгоритм имеет следующий вид. m=1; i1=1; +-----------for j=N to 2 -----------+ | X=K[m]; | | | | +---------for i= i1 to j -------+ | | | | | | | Поиск максимума Х=K[m] среди | | | | элементов K[i]. | | | | Формирование указателей L[i] | | | | для элементов, лежащих между | | | | i1+1 и j | | | +-------------------------------+ | | K[m]=K[j]; K[j]=X; i1=m; m=L[m]; | +-----------------------------------+ Время работы алгоритма t примерно оценивается формулой: t=a*Nэ + b*N*logN где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 3.2. Пирамидальная сортировка. Идея использования информации, полученной при вычислении максиму- ма на предыдущем шаге алгоритма выбора, реализована в алгоритме пи- рамидальной сортировки. Пусть исходный файл, взятый для примера: 503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 представлен в виде бинарного дерева, описывающего турнир с выбы- ванием, аналогичный спортивным соревнованиям. Элемент "побеждает" в соревновании двух элементов файла, если его ключ больше. Меньший ключ, "проигрывая" соревнование, выбывает из дальнейшей борьбы за максимальное значение. Дерево имеет следующий вид. 908 703 897 653 426 612 765 275 503 87 154 509 170 677 512 61 В данном бинарном дереве каждый предок больше обоих своих потом- ков, и в корне находится наибольший ключ. Такое дерево, названное пирамидой, и определило название метода. Структуру данных для представления пирамиды удобно выбрать в виде последовательного списка ключей, так что для каждого ключа K[i] его правый и левый сыновья находятся в позициях 2*i и 2*i+1 (ключи K[2*i] и K[2*i+1]). Например, вышеприведенная пирамида из 16 ключей отображается таким последовательным списком: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 908 703 897 653 426 612 765 275 509 87 154 509 170 677 512 61 +--++--++ || || ++--++--++---+--+---+---+---+ | | | +---+----++--++ | ++--++---+--+---+-----------+---+ | +----+---+----+---+ ++---+--+---+------------------+ +---+------------+---+ | | +-------------------+---+ После удаления максимального элемента из корня и переноса его в выходной массив необходимо скорректировать пирамиду так, чтобы в корне был следующий максимальный элемент, а каждый предок был больше своих потомков. Например, после удаления ключа 908 последний элемент в массиве данных - 61 - переместится на его место (в начало массива), и затем структура данных должна быть преобразована к виду, соответсвующему новой пирамиде. 897 703 765 653 426 612 677 275 503 87 154 509 170 61 512 Выходной массив можно формировать в конце исходного массива дан- ных. Алгоритм содержит два последовательных этапа: построение пирамиды и выбор элементов из корня пирамиды с последующим ее восстановлени- ем. Опишем сначала алгоритм восстановления. Если корень меньше хотя бы одного из своих потомков, то меняем местами корень и больший из потомков и применяем эту процедуру последовательно ко всем поддеревь- ям, в которых мы заменили корень. Этап построения пирамиды можно вывести из этапа восстановления. Исходный файл можно представить как набор тривиальных пирамид, сос- тоящих из одного элемента. Последовательно объединяя их по алгоритму восстановления, мы в конце концов приходим к полной пирамиде. Алгоритм пирамидальной сортировки имеет следующий вид. Через |N/2| обозначено ближайшее целое, меньшее N/2. + + l=|N/2|+1 ; r=N; + + +=======<==+ then if(l > 1) | else +=====<=========+==========+=====>==============+ +-----------+--------------------------+---------+ +--------+--------+ | Построение пирамиды | | |Выбор элемента из| +--------------------------------------+---------| |корня пирамиды | |l=l-1; X=K[l]; | | +-----------------| |j=l;<==========<======================+==<===<==++| X=K[r]; | |i=j;<=======<=========================+=+ ||| K[r]=K[1]; | |j=2*j; | | ||| r=r-1; +-------+| | +-----------------------------+-+-----+ ||| if(r=1)|K[1]=X;|| | | +-------+ | | | ||| else =+|Конец; || |if(j if(X>=K[j]) |K[i]=X; ++ | | | | | | +=======>====| | | | | | | | | +--------+ | | | | | | | | | | | | | | +-----------+ | | | | | | |else|K[i]= K[j];+>====>=+ | | | | | | +-----------+ | | | +----+-+------------------------------+ | | +--------+-+-----+ | |else| if(j=r)+ | | | | | else ==>=+ | | | +----------------+ | +------------------------------------------------+ Проиллюстрируем работу алгоритма на примере файла из 16 элемен- тов: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 l r X ------------------------------------------------------------------------ + + 503 87 512 61 908 170 897|275 653 426 154 509 612 677 765 703| 8 16 275 + + + + 503 87 512 61 908 170| 897 703 653 426 154 509 612 677 765 275| 7 16 897 + + + + 503 87 512 61 908|170 897 703 653 426 154 509 612 677 765 275| 6 16 170 + + + + 503 87 512 61|908 612 897 703 653 426 154 509 170 677 765 275| 5 16 908 + + + + 503 87 512|61 908 612 897 703 653 426 154 509 170 677 765 275| 4 16 61 + + + + 503 87|512 703 908 612 897 275 653 426 154 509 170 677 765 61| 3 16 512 + + + + 503|87 897 61 908 612 765 703 653 426 154 509 170 677 512 61| 2 16 87 + + + + |503 908 897 703 426 612 765 275 653 87 154 509 170 677 512 61| 1 16 503 + + + + |908 703 897 653 426 612 765 275 503 87 154 509 170 677 512 61| + + Пирамида сформирована, начало этапа выборки элементов + + |908 703 897 653 426 612 765 275 503 87 154 509 170 677 512|908 1 15 61 + + + + |897 703 765 653 426 612 677 275 503 87 154 509 170 61|897 908 1 14 512 + + + + |765 703 677 653 426 612 512 275 503 87 154 509 170|765 897 908 1 13 61 + + + + |703 653 677 503 426 612 512 275 61 87 154 509| 703 765 897 908 1 12 170 + + ....................................................................... + + |61| 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 1 1 61 + + На этапе выбора элементов из пирамиды они помещаются в конец фай- ла на освобождающиеся места. Полученный на последнем этапе файл яв- ляется упорядоченным по возрастанию. Время работы алгоритма t примерно оценивается формулой: t=a*N*logN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 4. Сортировка посредством слияния Алгоритмы сортировки этого класса основываются на объединении нескольких (часто двух) уже упорядоченнх файлов. Рассмотренные далее алгоритмы выбирают из исходного файла упорядоченные отрезки и объ- единяют их в более длинные. 4.1. Естественное двухпутевое слияние Этот алгоритм ищет упорядоченные отрезки с двух концов файла и переписывает их по очереди также в оба конца. Повторяя эту процедуру в цикле, мы приходим к середине файла, что означает окончание сорти- ровки. Проиллюстрируем работу алгоритма на примере файла из 16 эле- ментов: +-<---------------------------------------------------<-1-+ | +-2->-------------------------------------->-+ | | | +-<----------------------------<-3+ | | | | | +4->----------------->+ | | | | | | | +<----<5+ | | | | 503|87 512|61 908|170 897|275 653|426 154|509|612|677|765 703 -> -> -> -> -> <- <- <- <- <- Черточками разделены упорядоченные отрезки, стрелками показаны направления урорядочения внутри отрезков. На первом шаге сливаются отрезки 503 слева и 703 765 справа в один отрезок, который записыва- ется в левый конец файла, на втором шаге сливаются отрезки 87 512 слева и 677 справа, которые записываются в правый конец файла и т.д. Это показано на рисунке линиями со стрелками и номерами действий. В результате файл принимает следующий вид: 503 703 765| 61 612 908| 154 275 426 |653| 897 509 170 |677 512 87 -> -> -> -> <- <- <- Дальнейшие шаги дают следующие результаты: 87 503 512 703 765 |154 275 426 |653 | 908 897 612 509 170 61 -> -> -> <- <- 61 87 170 503 509 512 612 677 703 765 897 | 908 | 653 426 275 154 -> -> <- <- 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 | 908 | -> <- Рассмотрим алгоритм. Для хранения второго "экземпляра" файла об- разована новая область, располагающаяся вслед за исходной областью K[1], K[2], ... K[N] c индексами от N+1 до 2*N: K[N+1] ... K[2*N]. Элементы файла пересылаются из одной области в другую, меняя направ- ление пересылки. Для запоминания направления пересылки служит пере- менная s, принимающая значения TRUE и FALSE попеременно. Другой ло- гический признак f служит сигналом продолжения-окончания алгоритма, если все области слились в конце концов в одну. Переменная d прини- мает попеременно значения +1 -1 и указывает направление просмотра файла: вперед или назад.Операция <-> обозначает обмен значениями двух переменных. Операция + обозначает инверсию логической перемен- ной или выражения. s=true; +-----------------------------------------------do--------------------+ | then if(s) else | | +=========<===+===>===============+ | |+--+-----------------+ +-------------+------+ | ||i=1;j=N;k=N+1;l=2*N;| |k=1;l=N;i=N+1;j=2*N;| | |+--+-----------------+ +-------------+------+ | | +=========>=======+====<==========+ | | d=1; f=false; | | +================>+<=========================================+ | | | then if(K[i]<=K[j]) else | | | | +=========<===+===>=============+ | | | |+--+----------------------+ | +----------------+ | | | || if(i=j) ==>====>=====>=+===>====+==>==|K[k]=K[i]; s=+s;+=+===>| | || | | +----------------+ | | | || K[k]=K[i]; | +--+----------------------+ | | | || k=k+d; | | K[k]=K[j]; | | | | || i=i+1; | | k=k+d; | | | | || if(K[i-1] <= K[i])=>+ | | j=j-1; | | | | ++=============<=======+ | | if(K[j+1] <= K[j])=>====+=+ | | || +-------------do-----+ | | +-------------do-----+ | | | || | K[k]=K[j]; | | | | K[k]=K[i]; | | | | || | k=k+d; | | | | k=k+d; | | | | || | j=j-1; | | | | i=i+1; | | | | || +-while(K[j+1]<=K[j])+ | | +-while(K[i-1]<=K[i])+ | | | |+-----------+-------------+ +---------------------+---+ | | | +=======>+<================<==============+ | | | +----+-------------------+ | | | | f=true; d=-d; k <-> l; | | | | +----+-------------------+ | | +=====================+ | +-------------------------------while(f) -----------------------------+ +----------------------------------------------+ if(+s)| Пересылка K[N+1]...K[2*N] в K[1]...K[N] | +----------------------------------------------+ Конец алгоритма; Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. 4.2. Простое двухпутевое слияние. В алгоритме естественного двухпутевого слияния упорядоченный от- резки файла определялись случайным расположением элементов в исход- ном файле. В данном алгоритме длина отрезков фиксируется на каждом шаге. В исходной файле все отрезки имеют длину 1, после первого шага она равна 2, после второго 4, после третьего - 8, после к-го шага - 2 в степени к. Иллюстрация работы алгоритма приведена ниже. Исходный файл имеет вид: 503| 87|512|61 |908|170|897|275|653|426|154|509|612|677|765|703 Черточками разделены отрезки. Стрелками обозначено направление упорядочения. В дальнейшем файл преобразуется следующим образом. 503 703|512 677|509 908|426 897|653 275|170 154|612 61|765 87 -> -> -> -> <- <- <- <- 87 503 703 765|154 170 509 908|897 653 426 275|677 612 512 61 -> -> <- <- 61 87 503 512 612 677 703 765|908 897 653 509 426 275 170 154 -> <- 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908 -> Рассмотрим алгоритм. Для хранения второго "экземпляра" файла об- разована новая область, располагающаяся вслед за исходной областью K[1], K[2], ... K[N] c индексами от N+1 до 2*N: K[N+1] ... K[2*N]. Элементы файла пересылаются из одной области в другую, меняя направ- ление пересылки. Для запоминания направления пересылки служит пере- менная s, принимающая значения TRUE и FALSE попеременно. Переменная p имеет значение размера отрезков, которые будут сливаться на предс- тоящем шаге, q и r - количества неслитых еще элементов в отрезках. Переменная d принимает попеременно значения +1 -1 и указывает нап- равление просмотра файла: вперед или назад.Операция  обозначает об- мен значениями двух переменных. Операция + обозначает инверсию логи- ческой переменной или выражения. Алгоритм имеет следующий вид. s=true;p=1; +-------------------------------------------------do-------------------+ | then if(s) else | | +=========<===+===>===============+ | | +--+-----------------+ +-------------+------+ | | |i=1;j=N;k=N+1;l=2*N;| |k=1;l=N;i=N+1;j=2*N;| | | +--+-----------------+ +-------------+------+ | | +=========>=======+====<==========+ | | d=1; q=p; r=p; | | +==============>==+==<=======================================+ | | | if(K[i] <= K[j]) | | | | then | else | | | | +=========<===+===>=============+ | | | |+--+----------------------+ +--+----------------+ | | | || k=k+d; | | k=k+d; | | | | || K[k]=K[i]; | | K[k]=K[j]; | | | | || i=i+1; | | j=j-1; | | | | || q=q-1; | | r=r-1; | | | | || if(q>0)============>+ | | if(r>0)===========+=======+ | | ++=============<=======+ | | +----------do--+ | | | || +---------do---+ | | | k=k+d; | | | | || | k=k+d; | | | | if(k=l)=>==+ | | | | || | if(k=l) ==>==+=======+==>+<+==+=========<==+ | | | | || | K[k]=K[j] | | | | | K[k]=K[i] | | | | || | j=j-1;r=r-1; | | | | | i=i+1; q=q-1;| | | | || +while(r>0)----+ | | | +while(q>0)----+ | | | |+-----------+-------------+ | +-----------+-------+ | | | +=======>+<=======+========<====+ | | | +------------------+-----+ ++-----+ | | +<=| q=p;r=p;d=-d; k <-> l; | |p=p+p;| | | +------------------------+ |s=+s; | | | ++-----+ | +-----------------------------------+----while(p s=0; t=N+1; | p=L[s]; q=L[t]; | if(q=0) Конец алгоритма; | +=====>==================+=========<==================+==<=+ | | if(K[p]<=K[q]) | | | | then | else | | | | +===============<===+====>============+ | | | | |L[s]|=p; |L[s]|=q; | | | | s=p; p=L[p]; s=q; q=L[q]; | | | | if(p>0) =>+ if(q>0) =>=====+ | | +====<======+ | | |L[s]|=q; L[s] =p; | | s=t; s=t; | | +===<=========+ +===<=========+ | | t=q; q=L[q]; | t=p; p=L[p]; | | | if (q>0) =>====+ if (p>0) =>====+ | | else =====>=====================+ else =>=+ | | +==<==========+ | | p=-p; | | q=-q; | | if(q=0) | | then | else | | +====================<====+====>==================+ | |L[s]|=p; |L[t]|=0; +======<====+ Переменная s является текущим указателем в списке, полученном от слияния двух частичных списков, p - указатель на элемент одного из сливаемых списков, q - другого, t - рабочая переменная. Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. Этот метод допускает естественную модификацию, заключающуюся в том, что вместо начальной установки длин всех списков, равных 1 ( оператор L[i]=-(i+2); ), анализируется естественное упорядочение участков исходного файла, и длины устанавливаются максимально воз- можными. 5. Распределяющая сортировка Эта группа методов использует стратегию, прямо противоположную методам слияния. Ключи K[i] элементов файла рассматриваются в этом алгоритме как некоторые последовательности из s символов в известном алфавите K=(A1,A2,A3,...,As). Например, такой порядок используется для расположения слов в словаре. Если множество слов упорядочить сначала по правой букве, затем, не меняя порядка по правой букве, упорядочить их по следующей букве и т.д. до конца слова, то слова будут расположены в лексикографическом порядке. Можно начинать выбор букв как с конца, так и с начала слов. В процессе упорядочивания по букве множество слов разбивается на подмножества с одинаковыми зна- чениями данной буквы, а затем подмножества снова объединяются в одно множество в порядке, соответствующем алфавитному порядку для значе- ний этой буквы. Распределение множества по подмножествам и дало наз- вание этой группы методов. Алгоритм имеет следующий вид. Функция АДР(переменная) возвращает указатель на переменную. Функция ЭЛЕМ(указатель) позволяет выполнять операции над элементом файла,на который указывает аргумент функции. Подмножества, отсортированные по одной букве ключа, хранятся в виде М очередей, где М - количество возможных значений каждой буквы. Для каждой из М очередей существует два массива указателей: BOTM[0] ... BOTM[N] и TOP[0] ... TOP[M], указывающие соответственно на начала и концы очередей-подмножеств.BOTM[0] указывает в конце алгоритма на начало объединенного списка. Каждый элемент файла имеет поле ключа K[i] и поле связи L[i], указывающее на следующий элемент в отсорти- рованном файле. Символом @ обозначен пустой указатель. Его конкрет- ное значение может быть выбрано произвольно и использоваться в алго- ритме только в этом смысле. p=АДР(K[N]);j=N; +---------------- for k=1 to s ---------------------------------------+ | +-------------------+ | | for i=0 to M |TOP[i]=АДР(BOTM[i])| | | |BOTM[i]=@; | | | +-------------------+ | | | | | +=>=+=========================================<==================+ | | | i=(k-я младшая буква ключа, на который указывает переменная p) | | | | | | | | L[ЭЛЕМ(TOP[i])]=p; | | | | TOP[i]=p; | | | | if(k=1) | | | | then | else | | | | +==<==+=================>=====+ | | | | j=j-1; if(p + @) p=L[ЭЛЕМ(p)]; ==>====+ | | | if(j + 0) p=АДР(K[j];=>+ else ===>+ | | +==<======================+ | | | else ================>===+===<===========+ | | | | | p=TOP[0] | | +-for i=1 to M-1-----+ | | | if(BOTM[i]=@)===>==| | | | L[ЭЛЕМ(p)]=BOTM[i] | | | | p=TOP[i] | | | +--------------------+ | | L[ЭЛЕМ(p)]=@ | | p=BOTM[0] | +---------------------------------------------------------------------+ Работу алгоритма проиллюстрируем на примере файла из 16 элемен- тов, сортировка будет проводится по цифрам ключей, начиная с млад- шей. Исходный файл: 503 87 512 61 908 170 897 275 653 426 154 509 612 677 765 703 Файл после 1-го прохода (k=1) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] +-+--+ +--+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-++ +-+-+ +-+-+ |170 | | 61 | |512| |503| |154| |275| |426| |87| |908| |509| +-+--+ +--+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-++ +-+-+ +-+-+ | | +-+-+ +-+-+ | +-+-+ | +-+-+ | | | | |612| |653| | |765| | |897| | | | | +-+-+ +-+-+ | +-+-+ | +-+-+ | | | | | +-+-+ | | | +-+-+ | | | | | |703| | | | |677| | | | | | +-+-+ | | | +-+-+ | | | | | | | | | | | | BOTM[0] | BOTM[2] | BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] Файл после 2-го прохода (k=2) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] +--+-+ +--+-+ +-+-+ | | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ | 509| | 512| |426| | | |154| |765| |677| | 87| |897| +--+-+ +--+-+ +-+-+ | | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +--+-+ | | | | +-+-+ +-+-+ +-+-+ | | | 908| +--+-+ | | | |653| | 61| |275| | | +--+-+ | 612| | | | +-+-+ +-+-+ +-+-+ | | +--+-+ +--+-+ | | | | | +-+-+ | | | 503| | | | | | | |170| | | +--+-+ | | | | | | +-+-+ | | +--+-+ | | | | | | | | | | 703| | | | | | | | | | +--+-+ | | | | | | | | | BOTM[0] | BOTM[2] | BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] Файл после 3-го прохода (k=3) TOP[0] TOP[1] TOP[2] TOP[3] TOP[4] TOP[5] TOP[6] TOP[7] TOP[8] TOP[9] +--+-+ +--+-+ +-+-+ | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ | 87 | | 170| |275| | |426| |512| |677| |765| |897| |908| +--+-+ +--+-+ +-+-+ | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +--+-+ | | | | +-+-+ +-+-+ +-+-+ | | | 61| +--+-+ | | | |509| |653| |703| | | +--+-+ | 154| | | | +-+-+ +-+-+ +-+-+ | | | +--+-+ | | | | | | | | | | | | | +-+-+ +-+-+ | | | | | | | | |503| |612| | | | | | | | | +-+-+ +-+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | BOTM[0] | BOTM[2] | BOTM[4] BOTM[6] BOTM[8] BOTM[1] BOTM[3] BOTM[5] BOTM[7] BOTM[9] После 3-го прохода видно, что сцепление всех очередей от 0 до 9 дает отсортированный файл. Время работы алгоритма t примерно оценивается формулой: t=a*N + b где a,b - неизвестные константы, зависящие от программной реализа- ции алгоритма. ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА Постановка задачи. Имеется N элементов-записей в исходном файле, каждая из которых сопровождается ключом поиска K[1] ... K[N] и неко- торой информационной частью, которую мы можем не рассматривать без потери общности. Требуется найти позицию ключа, имеющего заданное значение X. Запросы на поиск поступают последовательно и в некоторых случаях известны вероятности поступления каждого из них P[1] ... P[N]. В зависимости от количества элементов файла N, диапазона и равномерности распределения значений ключей K[i], вероятностей зап- росов на поиск конкретных значений Х наиболее подходящим может ока- заться один из известных методов и структур данных, которые будут описаны ниже. 6. Последовательный поиск Название этой группы методов произошло от использования последо- вательного списка в качестве структуры данных для хранения ключей. Список называют упорядоченным, если он упорядочен по значениям клю- чей, в противном случае он не называется упорядоченным, хотя некото- рый порядок ему можно придать за счет размещения в начале списка элементов, которые ищутся наиболее часто, то есть в порядке убывания вероятностей запросов P[1] ... P[N]. 6.1. Последовательный поиск в неупорядоченном файле Алгоритм поиска имеет вид: +------------for i=1 to N--------------------+ |if(X=K[i]) Конец: поиск удачен. | +--------------------------------------------+ Конец: поиск неудачен. Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. Среднее время удачного поиска можно значительно сократить, если вероятности появления запросов на поиск различных ключей сильно от- личаются друг о другаи и ключи располагать в порядке убывания веро- ятностей. Алгоритм в этом случае не изменяется, но должен быть пред- варительный этап упорядочения списка. Также предполагается, что но- вые ключи при неудачном поиске не вставляются в список. 6.2. Последовательный поиск по связанному списку. Вероятности появления запросов на поиск часто не известны зара- нее. В этом случае можно использовать эмпирический алгоритм, дающий на практике хорошие результаты: каждый раз при удачном поиске най- денный ключ переставляется в начало списка. Естественно такие перес- тановки удобно делать на связанном списке. Каждому ключу K[i] соот- ветствует поле связи L[i], указывающее на следующий логически за ним ключ. На первый элемент указывает поле связи L[0]. +----+----+ +----+----+ +----+----+ |K[1]|L[1]+--> ... ->|K[i]|L[i]+->- ... -->|K[N]|L[N]+-> =0 +-+--+----+ +----+----+ +----+----+ ++---+ |L[0]| +----+ Алгоритм имеет следующий вид. +----+----+ +-----+-----+ |K[m]|L[m]+-|K[lm]|L[lm]+- m=0; lm=L[m]; +----+----+ +-----+-----+ +-----------while (lm + 0) do -----------------+ | +--------------------------------+ | | | Поиск удачен.Перестановка | | |if(X=K[lm])| ключа K[lm] в начало списка | | | +--------------------------------| | | |if (m + 0) then | | | |{L[m]=L[lm];L[lm]=L[0];L[0]=lm} | | | | | | | |Конец алгоритма. | | | +--------------------------------+ | | m=lm; lm=L[m]; | +----------------------------------------------+ Конец: поиск неудачен. Этот алгоритм легко модифицируется и для случая, когда после не- удачного поиска ключ Х должен быть вставлен первым в список. Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 6.3. Последовательный поиск в упорядоченном файле Если расположить ключи в возрастающем порядке, то время неудачно- го поиска можно существенно сократить. В простейшем алгоритме поиска в упорядоченном файле поиск прекращается, если при последовательном просмотре величмна Х становится больше или равной очередному ключу K[i]. В среднем при этом сокращается время неудачного поиска до N/2, среднее время удачного поиска остается по-прежнему равным N/2. Алгоритм имеет вид: +----- for i=1 to N --------------+ |if(X==================>| |if(X=K[i]) Конец: поиск удачен. | |Конец: поиск неудачен | +---------------------------------+ Время работы алгоритма t примерно оценивается формулой: t=a*N где a - неизвестная константа, зависящая от программной реализа- ции алгоритма и не зависящая для данного алгоритмаот результата поиска: удачен-неудачен. 6.4. Бинарный поиск в упорядоченном файле. Алгоритм предполагает деление упорядоченного списка ключей попо- лам до тех пор, пока в результате очередного деления число элементов в отрезке файла не уменьшится до одного. В этом случае уже можно сказать, был поиск удачным или нет. Алгоритм имеет вид: l=1; u=N; +------------ while(u>=l) -------+ |i=|(l+u)/2|; | | + + | |if(X======| |if(X>K[i]] l=i+1; ======>======| |if(X=K[i]] Конец: поиск удачен.| +--------------------------------+ Конец: поиск неудачен. Время работы алгоритма t примерно оценивается формулой: t=a*logN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. Лучших результатов не может дать ни один метод, основанный на срав- нении ключей, появляющихся с равной вероятностью.Однако, метод пред- назначен только для поиска, как и все методы, основанные на структу- ре исходного файла в виде последовательного списка. При включении новых ключей очевидны большие затраты по пересылке элементов. 6.5. Однородный бинарный поиск Эта модификация бинарного поиска требует сохранения таблицы значений величин D[1] ... D[max] max= |logN|+2. Эти величины отражают возможное + + изменение текущего индекса i на каждом шаге поиска i=i(+-)d, где d - один из элементов массива D. При этом может достигаться экономия времени за счет более эффективной программы. Схема алгоритма имеет вид. +-----------------------------------------------------------------+ | j-1 j | |Сформировать массив D, D[j]=|(N + 2 )/2 | ,j=1,2,..., |logN|+2| | + + + + | +-----------------------------------------------------------------+ i=D[1]; j=2; +====================================<======+ | +--------------------------------+| if(X====++ +--------------------------------+| +--------------------------------+| if(X>K[i]] |if(D[j]=0) Конец:поиск неудачен.|| |else i=i+D[j];j=j+1; ======>====++ +--------------------------------+ if(X=K[i]] Конец: поиск удачен. Время работы алгоритма t примерно оценивается формулой: t=a*logN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 6.6. Интерполяционный поиск Алгоритм интерполяционного поиска предполагает, что исходный файл упорядочен по величинам ключей поиска. Идея алгоритма состоит в том, что делается предположение о равномерном распределении величин в некотором их диапазоне от u до l. Поэтому, зная величину Х ключа поиска, можно предсказать более точное положение искомой записи, чем просто в середине некоторого отрезка файла. Формула нахождения положения следующего элемента для сравнения следует из деления длины отрезка u-l пропорционально величинам разностей ключей K[u]-K[l] и X-K[l]. Интерполяционный поик ассимптотически предпочтительнее бинарного, если только соблюдается гипотеза о равномерном распределении величин ключей. Алгоритм имеет вид: l=1; u=N; while(u>=l) +------------------------------------+ | i=l+|(u-l)*(X-K[l])/(K[u]-K[l])| | | + + | |if(X==========| |if(X>K[i]] l=i+1; ======>==========| |if(X=K[i]] Конец: поиск удачен. | +------------------------------------+ Конец: поиск неудачен Время работы алгоритма t примерно оценивается формулой: t=a*logN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 7. Поиск по бинарным деревьям Явное использование структуры данных в виде бинарного дерева поз- воляет эффективно производить операции не только поиска, но и встав- ки новых элементов, а также удаления. В структуре дерева каждый эле- мент имеет кроме ключа K[i] две связи: LL[i] - указатель (индекс) на левое поддерево и RL[i] - указатель (индекс) на правое поддерево. Пустой указатель @ соответствует пустому значению указателя, в конеч- ном узле - листе - оба указателя равны @. 7.1. Поиск по бинарному дереву. Схема алгоритма соответствует двум операциям: поиску (удачному и неудачному) и включению в дерево нового элемента. Для различения ре- жима включения при неудачном поиске и режима просто поиска в алго- ритме используется условие "Поиск?". В программе этот режим опреде- ляется при ее запуске в диалоге с пользователем. Логическая перемен- ная f служит для запоминания последней пустой связи, которая привела к неудачному поиску. Значение false соответствует левой пустой свя- зи, true - правой. Схема алгоритма поиска и, возможно, вставки имеет следующий вид. Функция avail() выделяет место в памяти для нового элемента в случае вставки. p = индекс элемента, стоящего в корне дерева +=============>========+===========<============================+ | if(X====+ | | | if(X=K[p]) Конец:удачный поиск | | if(LL[p]+@) p=LL[p]=>=+ if(RL[p]+@) p=RL[p]======>=====+ +=======================+ else f=true =>+ else f=false =============>===+====<=========+ then if(Поиск?) ======>=================+ q=avail(); | K[q]=X; | LL[q]=RL[q]=@; | if(f) RL[p]=q else LL[p]=q; | p=q; | Конец: вставка элемента | Конец:неудачный поиск=============<+ Время работы алгоритма t примерно оценивается формулой: t=a*lgN где a - неизвестная константа, зависящая от программной реализа- ции алгоритма, а также от результата поиска: удачен-неудачен. 7.2. Удаление из бинарного дерева Предполагается, что дерево создано алгоритмом 7.1. Узел p являет- ся предком удаляемого узла q. В алгоритме используется переменная pq, которая является указателем на поле той связи узла p, которая указывает на q. Функция ЗНАЧ(pq) используется в смысле самого поля связи, на которое указывает pq. Алгоритм имеет вид. t=q; if(RL[t]=@) then | else +===========<=====+===>==+ ЗНАЧ(pq)=LL[t]; | | if(LL[t]=@) | then | else | +========<==+==>====+ | ЗНАЧ(pq)=RL[t]; r=RL[t]; +==<====+===<========+ if(LL[r]=@) | then | else | +================<===============+===>==+ | LL[r]=LL[t];ЗНАЧ(pq)=r; s=LL[r]; ==<======+ | | if(LL[s]+@) r=s =>+ +==<====+ LL[s]=LL[t]; | LL[r]=RL[s]; | RL[s]=RL[t]; +===>===============>===+=<=+ ЗНАЧ(pq)=s; | +================<=====+ +-------+----------+ | Освободить память| | узла t | +------------------+ Конец алгоритма 7.3. Построение оптимальных бинарных деревьев поиска Деревья, получаемые данным алгоритмом, минимизируют цену дерева - взвешенную длину путей в дереве. Весами узлов являются частоты (ве- роятности) P[1] P[2] ... P[N] поиска данного ключа, одного из K[1] K[2] ... K[N] (значения ключей упорядочены в порядке возрастания) или частоты (вероятности) попадания искомого значения Х в промежуток между соседними значениями ключей Q[0] Q[1] ... Q[N]. Узлы занумеро- ваны от 1 до N. Алгоритм состоит из двух этапов. На первом этапе вычисляется мат- рица размером (N+1)*(N+1), каждая строка и столбец которой соответс- твует узлу (строка и столбец 0 соответствуют внешнему узлу - листу, отражающему значения ключа поиска меньше наименьшего K[1]). В каждом элементе матрицы с индексами [i,j] хранятся три параметра оптималь- ного поддерева,образованного множеством узлов от узла i до узла j. R[i,j] есть корень оптимального поддерева, W[i,j] есть сумма весов узлов, C[i,j] есть цена поддерева. Из оптимальных поддеревьев в ре- зультате составляется оптимальное дерево. +--------------for i=0 to N -------------------------------+ |R[i,i]=i; +----------------------------+| |W[i,i]=Q[i]; for j=i+1 to N | W[i,j]=W[i,j-1]+P[j]+Q[j]; || |C[i,i]=0; +----------------------------+| +----------------------------------------------------------+ +------------------------------+ for j=1 to N |C[j-1,j]=W[j-1,j];R[j-1,j]=j; | +------------------------------+ +--------------for d=2 to N ----------------------------------+ | | | +------------for j=d,N-----------------------------------+ | | | i=j-d; v=R[i,j-1]; min=C[i,v-1]+C[v,j]; kmin=v; | | | | +----------for k=v to R[i+1,j]----------------------+ | | | | | +----------------------+ | | | | | |if(C[i,k-1]+C[k,j] < min) | min= C[i,k-1]+C[k,j] | | | | | | | | kmin=k | | | | | | | +----------------------+ | | | | | +---------------------------------------------------+ | | | | C[i,j]=min+W[i,j]; | | | | R[i,j]=kmin; | | | +--------------------------------------------------------+ | +-------------------------------------------------------------+ На втором этапе на основе этой матрицы формируется традиционная структура данных для представления дерева. Каждый узел i имеет три поля: значение ключа K[i], ссылку на но- мер узла - корня левого поддерева LL[i], ссылку на номер узла - кор- ня правого поддерева RL[i]. Ссылка @ есть пустая ссылка на лист де- рева. В схеме используются две функции: A(v) - адрес или индекс в массиве некоторой переменной v и ЗНАЧ(u) - значение переменной по адресу u. uk - переменная, которая имеет значение номера корнево- го узла оптимального дерева. Стек используется для хранения троек (u,i,j), соответствующих поддеревьям, где u - адрес или индекс в массиве корня данного поддерева, i,j - начальный и конечный индексы поддерева. Схема второго этапа имеет следующий вид. i=0; j=N; u=A(uk); Опустошить стек. | +========<================================+ v=R[i,j]; | ЗНАЧ(u)=v; | if(j>v) | then | else | +======<=====+=====>===================+ | | | | u=A(RL[v]); ЗНАЧ(u)=j; | (u,v+1,j) => в стек; | | +======>=====+==============<==========+ | u=A(LL[v]); | j=v-1; | if(j>i) ====>===============================>+ +----------------------------------+ | else |if(i=0) ЗНАЧ(u)=@ else ЗНАЧ(u)=i; | | +----------------------------------+ | if(стек не пуст) извлечь из стека (u,i,j);===>+ Конец алгоритма. Для примера рассмотрим построение оптимального дерева из 6 узлов со следующими частотами P и Q. +----+----+----+----+----+----+----+----+ | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | +----+----+----+----+----+----+----+----| |P[i]| - | 9 | 1 | 4 | 1 | 3 | 2 | +----+----+----+----+----+----+----+----| |Q[i]| 0 | 0 | 0 | 0 | 0 | 0 | 0 | +----+----+----+----+----+----+----+----+ Работа алгоритма представлена в виде матрицы. В каждой клетке ма- трицы указано значение R[i,j], W[i,j], C[i,j] и, возможно, пределы значений индекса k. Cимволом ш отмечено то значение k, которое, взя- тое в качестве корня, дает оптимальное поддерево, так как ему соот- ветствует минимальная цена С[i,j]=W[i,j]+C[i,k-1]+C[k,j]. Просмотр клеток ведется по диагоналям, по возрастанию значений d=0,1,...,6 . 0 1 2 3 4 5 6 +-----+-----+----------+----------+----------+----------+---------+ |R 0 | 1 | 1 | 1 | 1 | 1 | 3 | 0|W 0 | 9 | 10 | 14 | 15 | 18 | 20 | |C 0 | 9 | 10+1=11 | 14+6=20 | 15+8=23 | 18+15=33 | 20+20=40| | | | k=ш1,2 | k=ш1,2,3 | k=ш1,2,3 | k=ш1,2,3 | k=1,2,ш3| +-----+-----+----------+----------+----------+----------+---------| | | 1 | 2 | 3 | 3 | 3 | 3(5) | 1| | 0 | 1 | 5 | 6 | 9 | 11 | | | 0 | 1 | 5+1=6 | 6+2=8 | 9+6=15 | 11+10=21| | | | | k=2,ш3 | k=ш3 | k=ш3 | k=ш3,4,5| +-----+-----+----------+----------+----------+----------+---------| | | | 2 | 3 | 3 | 3 | 5 | 2| | | 0 | 4 | 5 | 8 | 10 | | | | 0 | 4 | 5+1=6 | 8+5=13 | 10+8=18 | | | | | | k=ш3,4 | k=ш3,4,5 | k=3,4,ш5| +-----+-----+----------+----------+----------+----------+---------| | | | | 3 | 4 | 5 | 5 | 3| | | | 0 | 1 | 4 | 6 | | | | | 0 | 1 | 4+1=5 | 6+3=9 | | | | | | | k=4,ш5 | k=5 | +-----+-----+----------+----------+----------+----------+---------| | | | | | 4 | 5 | 5 | 4| | | | | 0 | 3 | 5 | | | | | | 0 | 3 | 5+2=7 | | | | | | | | k=ш5,6 | +-----+-----+----------+----------+----------+----------+---------| | | | | | | 5 | 6 | 5| | | | | | 0 | 2 | | | | | | | 0 | 2 | +-----+-----+----------+----------+----------+----------+---------| | | | | | | | 6 | 6| | | | | | | 0 | | | | | | | | 0 | +-----+-----+----------+----------+----------+----------+---------+ Время работы алгоритма t примерно оценивается формулой: t=a*Nэ где a - неизвестная константа, зависящая от программной реализа- ции алгоритма. 7.4. Цифровой поиск по дереву В этом алгоритме предполагается, что искомый ключ Х представляет собой последовательность бит. Функция БИТС(Х) возвращает старший бит ключа Х. Функция СДВГЛ(Х) сдвигает Х на 1 бит влево,добавляя справа 0. Схема алгоритма имеет вид. p = индекс элемента, стоящего в корне дерева X1=X; +===============<=========================+ | | if(X=K[p]) Конец: удачный поиск; | b=БИТС(X1); X1=СДВГЛ(X1); | if(b) | 0 | 1 | +========<=+=============>==+ | | if(RL[p]+@) p=RL[p]=>=+=>=====+ if(LL[p]+@) p=LL[p]=>======>==+======>=============+ | | +====>=====+======<=========+ if(Поиск?) ======>=================+ q=avail(); | K[q]=X; | LL[q]=RL[q]=@; | if(b=0) LL[p]=q else RL[p]=q; | p=q; | Конец:вставка или неудачный поиск;<+ 7.5. Цифровой поиск для длинных ключей, хранимых в текстовом массиве (Патриция) Название Патриция(Patricia) произошло от сокращения: Practical Algorithm To Retrieve Information Coded In Alphanumeric. Ключи, по которым производится поиск, имеют вид текстовых фраз различной длины и хранятся в массиве TEXT. В узлах дерева поиска хранятся лишь ссыл- ки на TEXT, которые будем обозначать через KEY(p), где p - номер уз- ла. Поиск выполняется путем последовательного просмотра битов ключа поиска Х и "путешествия" по дереву в зависимости от их значения. Каждый узел p дерева кроме ссылки KEY(p) на массив TEXT содержит: - ссылки на левое LL(p) и правое RL(p) поддерево; - битовые признаки LTAG(p) и RTAG(p) для LL(p) и RL(p) соответс- твенно, обозначающие окончание поиска: если признак равен 0, то ссылка LL(p) или RL(p) не пуста и имеет обычный смысл; если при- знак равен 1, то ссылка выполнена на одного из предков этого узла или на него самого и обозначает необходимость окончания про- смотра дерева и обращения к массиву TEXT из этого узла; - значения SKIP(p), обозначающие количество бит в аргументе поис- ка, которые нужно пропустить перед сравнением в следующем узле, то есть номер следующего бита, по которому выполняется сравнение,есть не j+1 ( j - номер бита, по которому выполнялось сравнение в дан- ном узле p), а j+SKIP(p). Данный признак позволяет удалить из де- рева узлы, из которых ведет только одна ссылка, а другая пуста. Начальный узел поиска назван "голова" (head), узел head имеет только левую ссылку LL(head) и ccылку на массив TEXT - KEY(head). Через n обозначено количество бит в аргументе поиска Х. Через Х[i] обозначим i-й бит аргумента Х, через TEXT[i] - i-й бит в массиве TEXT, считая от от некоторой заданнойссылки на него из узла. Будем рассматривать два алгоритма: поиска (алгоритм П) и вставки новых узлов (алгоритм В). Второй алгоритм как составную часть использует первый. Схема алгоритма П имеет вид. p=head; j=0; +======>============+ +===========<===+ | q=p; p=LL(q); q=p;p=RL(p); | | if(LTAG(q)=1) if(RTAG(q)=1) | | then | else else | then | | +======<=+=========>===+====<=========+=====>==+ | | | j=j+SKIP(p) | | | | if(j>n) =====>=============+ | | | if(X[j]) | | | | 0 | 1 | | +=======+=================<====+====>==================+==>===+ +======>===============+=========<=============+ for i=KEY(p) to KEY(p)+n-1 +--------------------+ | if(TEXT[i]+X[i] ==+=>==+ +---+----------------+ | | l=i-KEY(p) | | Конец: удачный Конец: неудачный поиск поиск Cхема алгоритма В имеет вид. +----------------------------------------------------------------+ | Начальный шаг: выполняется при первом обращении к алгоритму В.| +----------------------------------------------------------------| | Занести в массив TEXT с индекса 1 первый аргумент поиска; | | KEY(head)=1; LL(head)=head; LTAG(head)=1; | +----------------------------------------------------------------+ Следующие шаги выполняются при каждом последующем входе. +------------------------------------------------------------------+ |Выполнить алгоритм П с выходом по неудачному поиску. | |Уменьшить длину ключа Х с n до величины l - числа совпавших при | |поиске бит. Снова выполнить алгоритм П с выходом на этот раз по | |удачному поиску. | +--------------------+---------------------------------------------+ r=AVAIL() - память для нового узла r. if(p есть левая ссылка для q) then | else +============<=====+========>======================+ LL(q)=r; RL(q)=r; t=LTAG(q); t=RTAG(q); LTAG(q)=0; RTAG(q)=0; +==================+===============================+ b = (l+1)-й бит Х if(b) 1 | 0 +===============+================================+ RTAG(r)=1; LTAG(r)=1; RL(r)=r; LL(r)=r; LTAG(r)=t; RTAG(r)=t; LL(r)=p; RL(r)=p; +===============+================================+ if(t) 0 | 1 +===============+================================+ SKIP[r]=(l+1)-j; SKIP[r]=(l+1)-(j-SCIP[p]); | SKIP[p]=j-(l+1); +===============+================================+ Конец: в дерево включена новая вершина r. Рассмотрим пример работы алгоритмов П и В. Пусть в дерево Патриции нужно последовательно включить следующие элементы: '0 ','А ','Б ','С '. В качестве конечного символа в каждом заказе на поиск используется символ пробела. В 16-ричном и двоичном виде заказы на поиск имеют следующий вид: '0 '= 4820=0100 1000 0010 0000 Шаг 1 'А '= 8020=1000 0000 0010 0000 Шаг 2 'Б '= 8120=1000 0001 0010 0000 Шаг 3 'С '= 9120=1001 0001 0010 0000 Шаг 4 Шаг 1. Х='0 ' Состояние дерева после шага 1. Дерево состоит только из головной вершины, в которой определены ссылки: на TEXT: KEY(h)=1 (на рисунке показан непосредственно текст '0 ', на который указывает ссылка), на левое поддерево: LL(h)=h и LTAG(h)=1. +>'0 ' +-+-+ +-->| h | | +-+-+ +--<--+ Состояние дерева после шага 2. Состояние дерева после шага 3. X='А ' X='Б ' +>'0 ' +>'0 ' +-+-+ +-+-+ +---------->| h | +---------->| h | | +-+-+ | +-+-+ | +=======+ | +=======+ | | +>'А ' | | +>'А ' | +---+-++ | +---+-++ | | 1 | +-+>| 1 | | |SKIP=1+<+ | | |SKIP=1| | +-+-+--+ | | | +-+-+--+ +--<+ +>---+ | +---+ +========+ | | +>'Б ' | +---+-++ | | 2 | | |SKIP=7+<+ | +-+-+--+ | +-------------<+ +>---+ На рисунке одинарными линиями показаны ссылки с TAG=1, а двойными - ссылки с TAG=0. Состояние дерева после шага 4. X='С ' +>'0 ' +-+-+ +---------->| h | | +-+-+ | +=======+ | | +>'А ' | +---+-++ +--+>| 1 | | | |SKIP=1| | | +--+-+-+ | +--<-+ +=>=====+ | | +>'C ' | +---+-++ | | 3 | | |SKIP=3+<-+ | +--+-+-+ | | +=<=====+ +->--+ | | +>'Б ' | +---+-++ | | 2 +<--+ | |SKIP=4| | | +-+--+-+ | +----<-+ +-->--+