3. Сортировка посредством выбора
Идея метода довольно проста: найти наибольший элемент файла и поставить его на место N, найти следующий максимум и поставить его на место N-1 и т.д. до 2-го элемента. Схема алгоритма имеет следующий вид.
Время работы алгоритма t примерно оценивается формулой:
t=a*N^2 + b*N*lgN
где a,b - неизвестные константы, зависящие от программной реализации алгоритма.
3.1. Использование связанного списка для хранения информации о промежуточных максимумах
В приведенном выше алгоритме максимум среди K[1] ... K[j-1] определяется в цикле от j-1 до 1 c целью обеспечить меньшее число обменов в случае равенства ключей и сохранении прежнего порядка равных элементов. Однако, если изменить порядок просмотра элементов на противоположный и изменить структуру данных, введя дополнительные указатели, можно примерно в два раза сократить число повторений в цикле поиска максимума. Каждый ключ K[i] снабжается указателем L[i] на элемент, максимальный среди первых i-1 элементов так, как показано ниже.
Тогда после обмена элементов K[j] и K[m] поиск следующего максимума можно осуществлять среди элементов K[L[j]] ... K[j-1], т.к. максимум может "обновиться" только за счет элементов, лежащих правее локального максимума. Таким образом среднее количество просматриваемых при поиске максимума элементов сокращается примерно в два раза.
Модифицированный алгоритм имеет следующий вид.
Время работы алгоритма t примерно оценивается формулой:
t=a*N^2 + b*N*lgN
где a,b - неизвестные константы, зависящие от программной реализации алгоритма.
3.2. Пирамидальная сортировка
Это алгоритм сортировки массива произвольных элементов; требуемый им дополнительный объём памяти не зависит от количества исходных данных. Время работы алгоритма —  в среднем, а так же в лучшем и худшем случаях.
Идея алгоритма:
• Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.
• Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать, превратив в пирамиду.
• Самый большой элемент пирамиды находится в её вершине.
• Отделяем вершинный элемент, и записываем его в конец результирующего массива.
• На место вершинного элемента записываем элемент из самого нижнего уровня дерева.
• Восстанавливаем (пересортировываем) пирамиду.
• Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...
• Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается, начиная с конца массива на освободившиеся от пирамиды места.
Пирамида
Возрастающей пирамидой называется почти заполненное дерево, в котором значение каждого элемента больше либо равно значений всех его потомков. Аналогично, в убывающей пирамиде значение каждого элемента меньше либо равно значений потомков.
Пример возрастающей пирамиды показан на рисунке:
Очевидно, самое большое значение в возрастающей пирамиде имеет корневой элемент. Однако, из свойств пирамиды не следует, что значения элементов уменьшаются с увеличением уровня. В частности, на рисунке 4 элемент со значением 3 на четвёртом уровне больше значений всех элементов, кроме одного, на третьем уровне.
Важной операцией является отделение последнего (в смысле нумерации) элемента от пирамиды. Нетрудно доказать, что в этом случае двоичное дерево остаётся почти заполненным, и все свойства пирамиды сохраняются.
Просеивание вверх
Рассмотрим теперь задачу присоединения элемента с произвольным значением к возрастающей пирамиде. Если просто добавить элемент в конец массива, то свойство пирамиды (значение любого элемента значения его родителя) может быть нарушено. Для восстановления свойства пирамиды к добавленному элементу применяется процедура просеивания вверх, которая описывается следующим алгоритмом:
если элемент корневой, или его значение  значения родителя, то конец;
меняем местами значения элемента и его родителя;
переходим к родителю, и выполняем для него этот же алгоритм, начиная с пункта 1.
Пример просеивания вверх добавленного элемента показан на рисунке:
После выполнения данной процедуры свойство пирамиды будет восстановлено, так как:
Если вновь добавленный элемент больше родителя, то он больше и второго потомка родителя (если второй потомок есть), так как до добавления нового элемента было выполнено свойство пирамиды, и родитель был не меньше своего потомка (на рисунке 5 слева: семёрка больше своего родителя — четвёрки, — поэтому она больше и второго потомка четвёрки — тройки). После обмена значений элемента и родителя свойство пирамиды будет восстановлено в поддереве, корнем которого является родитель с новым значением (например, после обмена местами семёрки и четвёрки, семёрка тройка и четвёрка будут образовывать правильное поддерево).
В результате обмена свойство пирамиды может быть нарушено в отношении родителя и родителя родителя (так как значение родителя стало больше). Процедура вызывается для родительского узла, чтобы восстановить это свойство.
Просеивание вниз
Что делать, если нам нужно заменить корневой элемент на какой-либо другой? В этом случае пирамидальную структуру двоичного дерева можно восстановить с помощью процедуры просеивания вниз:
если элемент листовой, или его значение  значений потомков, то конец;
иначе меняем местами значения элемента и его потомка, имеющего максимальное значение;
переходим к изменившемуся потомку, и выполняем для него этот же алгоритм, начиная с пункта 1.
Пример просеивания вниз показан на рисунке:
Построение пирамиды
Допустим, у нас есть произвольный набор из n элементов, и мы хотим построить из него пирамиду. Самый простой способ этого добиться — начать с пустой пирамиды, и добавлять в неё элементы один за другим, каждый раз вызывая процедуру просеивания вверх для нового элемента. Назовём этот метод построения пирамиды «методом просеивания вверх». Пример работы алгоритма показан на рисунке:
Рассчитаем быстродействие этого метода в самом плохом случае. Пусть массив уже отсортирован по возрастанию, и каждый добавляемый элемент вынужден просеиваться вверх до самого корня. Тогда при добавлении элемента номер i нам потребуется  операций. Мы делаем эту процедуру для всех i от 0 до  :
|
(1)
|
Оценим сумму в выражении (1) с помощью определённого интеграла:
|
(2)
|
Вычисляя интегралы, получаем:
|
(3)
|
Это означает, что:
|
(4)
|
На самом деле пирамиду можно построить быстрее. Для этого заполним дерево элементами в произвольном порядке (например, так, как они идут в массиве изначально), и будем его исправлять.
Заметим, что если у нас есть две пирамиды, то, если их соединить общим корнем, а затем просеять корень вниз, то мы получим новую большую пирамиду. Деревья, состоящие из одного элемента, заведомо являются пирамидами, поэтому начнём с набора листовых элементов, а затем будем соединять имеющиеся пирамиды попарно до тех пор, пока не получим одну большую пирамиду. Первый добавляемый корень имеет индекс  . Алгоритм следующий: «для всех i от  до 0 вызываем процедуру просеивания элемента вниз». Назовём этот метод построения пирамиды «методом просеивания вниз».
Вычислим быстродействие этого алгоритма в худшем случае. Пусть массив отсортирован по возрастанию, и каждый добавляемый корень должен быть просеян в самый низ строящейся пирамиды. Высота дерева примерно равна  , глубина залегания элемента номер i в дереве равна  , поэтому он будет просеиваться вниз  шагов. Тогда общее время построения пирамиды будет равно:
|
(5)
|
Оценивая сумму интегралами аналогично (2), (3), получим:
|
(6)
|
Отсюда следует, что для большого числа элементов  будет меньше, чем  . Более точные оценки дадут, что  для любых n, так как, во первых, при построении пирамиды методом просеивания вверх процедура просеивания вызывается в 2 раза больше раз, чем при построении методом просеивания вниз, и, во вторых, элементы с номерами от  до n просеиваются вверх на большее расстояние, чем расстояние, на которое просеиваются вниз элементы от от до 0. Поэтому в дальнейшем будем строить пирамиду методом просеивания вниз.
Сортировка
Имея построенную пирамиду, несложно реализовать сортировку. Так как корневой элемент пирамиды имеет самое большое значение, мы можем отделить его и поместить в отсортированный список. Вместо отсутствующего корневого элемента можно поставить последний (в смысле нумерации) элемент дерева и, просеяв его вниз, снова получить пирамиду.
В новой уменьшенной пирамиде корень имеет самое большое значение среди оставшихся элементов. Его снова можно отделить и поместить в отсортированный список перед имеющимися там элементами, и так далее.
Для хранения отсортированного списка будем использовать элементы исходного массива, освобождающиеся в результате уменьшения размера пирамиды. Алгоритм получается следующий:
1. Поменять местами значения первого и последнего элементов пирамиды.
2. Отделить последний элемент от дерева, уменьшив размер дерева на единицу (элемент остаётся в массиве).
3. Восстановить пирамиду, просеяв вниз её новый корневой элемент.
4. Перейти к пункту 1.
5. По мере работы алгоритма, часть массива, занятая деревом, уменьшается, а в конце массива накапливается отсортированный результат.
6. Теоретическое время работы этого алгоритма нетрудно оценить, если заметить, что пирамидальная сортировка (без учёта начального построения пирамиды) полностью аналогична построению пирамиды методом просеивания вверх, только производится «в обратном порядке»: пирамида не строится, а «разбирается» элемент за элементом, и элементы просеиваются не вверх, а вниз. Поэтому время работы алгоритма пирамидальной сортировки  без учёта времени построения пирамиды будет определяться аналогично формуле (4):
|
(7)
|
7. Тогда общее время сортировки (с учётом построения пирамиды) будет равно:
|
(8)
|
|
