ЧАСТЬ 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 равно примерно lg(j).Число пересылок элемен- тов при этом не изменяется и остается примерно равным N¤/4. Схема алгоритма бинарных вставок может быть получена небольшой модификацией схемы из раздела 6.4. Время работы алгоритма t примерно оценивается формулой: t=a*N¤ + b*N + c*N*lgN где 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+1] и m уменьшается на 1. Далее цикл по i продолжается с новым m. Экономия числа переносов элементов достигается за счет переносов сразу на m элементов. Время работы алгоритма t примерно оценивается формулой: t=a*N¤ + b*N + c*N*lgN где 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**1.25 где a - неизвестная константа, зависящая от программной реализа- ции алгоритма. 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]│ └────┘ Алгоритм имеет следущий вид: for j=N-1 to 1 ┌───────────────────────────┐ │ p=L[0]; q=0; X=K[j]; │ │ │ │ while(p>0 & X>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. Вставки в несколько связанных списков Идея метода основывается на предположении, что ключи в исходном файле имеют значения в некотором известном диапазоне и что в этом диапазоне они распределены довольно равномерно. Тогда по аналогии с методом вставки в один связанный список можно организовать несколь- ко, например, d списков. Величина d зависит от ожидаемого среднего количества элементов M в каждом списке то есть d=max/M,(max - диапа- зон ключей). Значение M по некоторым экспериментальным данным не следует делать меньше 9. При разработке программы нужно проанализи- ровать зависимость времени работы метода от параметра М для различ- ных исходных файлов и дать рекомендации по выбору оптимального зна- чения. Схема алгоритма имеет следующий вид. Через d обозначено коли- чество списков, массив B[1]...B[d] служит для хранения указателей на начала отдельных списков. Перед началом работы алгоритма элементы массива В предполагаются равными 0.Каждый i-й элемент исходного фай- ла содержит ключ K[i] и указатель L[i] на следующий элемент списка. Значение L[i]=0 соответствует последнему элементу в списке, указатель B[1] указывает на начало первого подсписка и одновременно на начало всего списка. Через minK обозначено минимальное значение ключа в файле, через М - среднее выбранное значение количества эле- ментов в подсписке. for j=N-1 to 1 ┌────────────────────────────────────────────┐ │ X=K[j]; d= (X-minK)/M+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 - неизвестные константы, зависящие от программной реализа- ции алгоритма.