           3. Сортировка посредством выбора

           Идея метода довольно проста:  найти наибольший  элемент  файла  и
        поставить  его на место N,  найти следующий максимум и поставить его
        на место N-1 и т.д.  до 2-го элемента. Схема алгоритма имеет следую-
        щий вид.

        for j=N to 2
       ┌───────────────────────────────────┐
       │ m=j; X=K[m];                      │
       │ for i=j-1 to 1                    │
       │ ┌───────────────────────────────┐ │
       │ │             ┌─────────────┐   │ │
       │ │ if(X<K[i])  │ X=K[i]; m=i;│   │ │
       │ │             └─────────────┘   │ │
       │ └───────────────────────────────┘ │
       │  K[m]=K[j]; K[j]=X;               │
       └───────────────────────────────────┘

           Время работы алгоритма t примерно оценивается формулой:

                   t=a*N¤ + b*N*lgN
        где a,b - неизвестные константы, зависящие от программной реализа-
        ции алгоритма.


           3.1. Использование связанного списка для хранения информации
                о промежуточных максимумах.

           В приведенном выше алгоритме максимум среди K[1] ... K[j-1] опре-
        деляется в цикле от j-1 до 1 c целью обеспечить меньшее число  обме-
        нов  в  случае равенства ключей и сохранении прежнего порядка равных
        элементов. Однако, если изменить порядок просмотра элементов на про-
        тивоположный  и изменить структуру данных, введя дополнительные ука-
        затели, можно примерно в два раза сократить число повторений в цикле
        поиска  максисмума.  Каждый  ключ K[i] снабжается указателем L[i] на
        элемент,  максимальный  среди первых i-1 элементов так, как показано
        ниже.

                                       указывает           указывает
                                       на                  на
        ┌────┐      ┌────┐     ┌────┐  элемент,    ┌────┐  элемент,
        │L[1]├> =1  │L[2]├>=1  │L[3]├> наибольший  │L[4]├> наибольший
        ├────┤      ├────┤     ├────┤  среди       ├────┤  среди      ...
        │K[1]│      │K[2]│     │K[3]│  первых      │K[4]│  первых
        └────┘      └────┘     └────┘  двух        └────┘  трех

           Тогда после  обмена элементов K[j] и K[m] поиск следующего макси-
        мума можно осуществлять среди элементов K[L[j]] ...  K[j-1]  ,  т.к.
        максимум может "обновиться" только за счет элементов, лежащих правее
        локального максимума. Таким образом среднее количество просматривае-
        мых  при поиске максимума элементов сокращается примерно в два раза.
        Модифицированный алгоритм имеет следующий вид.

        m=1;
        for j=N to 2
       ┌───────────────────────────────────┐
       │  X=K[m];                          │
       │  Lm=m;                            │
       │  for i= Lm to j                   │
       │ ┌───────────────────────────────┐ │
       │ │ Поиск максимума Х=K[m] и      │ │
       │ │ и формирование указателей L[i]│ │
       │ │ среди элментов, лежащих       │ │
       │ │ между Lm и j                  │ │
       │ └───────────────────────────────┘ │
       │  K[m]=K[j]; K[j]=X; m=L[m];       │
       └───────────────────────────────────┘


           Время работы алгоритма t примерно оценивается формулой:

                   t=a*N¤ + b*N*lgN
        где 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<r) │if(K[j]<K[j+1])│j=j+1; │     ║ ║     │ │╚╪════<══╝└───────┘│
       │        │               └─╥─────┘     ║ ║     │ │ └─────────────────┘
       │        │                 ║ ┌────────┐║ ║     │ │
       │        │    ╔>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*lgN + b*N
        где a,b - неизвестные константы, зависящие от программной реализа-
        ции алгоритма.
