           ЧАСТЬ 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 - неизвестные константы, зависящие от программной реализа-
        ции алгоритма.
