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] поиск следующего макси- мума можно осуществлять среди элементов 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(jif(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 - неизвестные константы, зависящие от программной реализа- ции алгоритма.