Таким образом, процесс выбора, в котором выполняется поиск наибольшего элемента, должен включать не менее п - 1 сравнений. Означает ли это, что для всех методов сортировки, основанных на п повторных выборах, число операций неизбежно будет порядка П(гг)? К счастью, лемма М применима только к первому шагу выбора; в дальнейшем можно использовать извлеченную ранее информацию. Например, в упр. 8 и 9 показано, что сравнительно простое изменение алгоритма S позволяет наполовину сократить среднее число сравнений.

Рассмотрим 16 чисел, представленных в табл. 1. Один из способов сэкономить время при последующих выборах - разбить все числа на четыре группы по четыре числа. Начать можно с определения наибольшего элемента каждой группы, а именно - с ключей

512, 908, 653, 765.

Тогда наибольший из этих четырех элементов (элемент 908) и будет наибольшим во всей последовательности. Чтобы получить второй по величине элемент, достаточно просмотреть 512, 653, 765 и остальные три элемента группы, содержащей 908; наибольший из {170, 897, 275} равен 897, и тогда наибольшим среди элементов

512, 897, 653, 765

является 897. Аналогично для того, чтобы получить третий по величине элемент, определяем наибольший из {170, 275}, а затем наибольший из элементов

512, 275, 653, 765

и т. д. Каждый выбор, кроме первого, требует не более 6 дополнительных сравнений. В общем случае, если N - точный квадрат, можно разделить массив на VN групп по -/N элементов. Любой выбор, кроме первого, требует не более чем -/N - 2 сравнений внутри группы ранее выбранного элемента плюс y/N- 1 сравнений среди "лидеров групп" Этот метод получил название квадратичный выбор; общее время его работы составляет порядка 0{NVN), что существенно лучше, чем N".

Метод квадратичного выбора впервые был опубликован в работе Е. И. Friend, JACM 3 (1956), 152-154. Э. Г. Френд указал, что его можно обобпщть и получить методы кубической, четвертой и более высоких степеней выбора. Например, метод кубического выбора состоит в том, чтобы разделить массив на больших групп, в каждой из которых содержится по малых групп по записей. Время работы будет пропорционально N\/N. Если развить эту идею, можно прийти к тому, что Френд назвал "выбор п-й степени" базирующийся на структуре бинарного дерева. Время выполнения сортировки по этому методу пропорционально NlogN; будем называть его выбором из дерева.

Выбор из дерева. Принципы сортировки посредством выбора из дерева будет легче понять, если воспользоваться аналогией с типичным "турниром с выбыванием". Рассмотрим, например, результаты соревнования по настольному теннису, показанные на рис. 22. В первом туре Ким побеждает Сэнди, а Крис побеждает Лу; затем в следующем туре Крис выигрывает у Кима и т. д.

Крис

Рис. 22. Турнир по настольному теннису.

На рис. 22 показано, что Крис - чемпион среди восьми участников. Для того чтобы определить это, потребовалось 8-1 = 7 матчей (т. е. сравнений). Пат вовсе необязательно будет вторым по силе игроком: любой из спортсменов, у которых выиграл Крис, включая даже проигравшего в первом туре Лу, может оказаться вторым по силе. Второго игрока можно определить, заставив Лу сыграть с Кимом, а победителя этого матча - с Патом. Всего двух дополнительных матчей достаточно для определения второго по силе игрока, исходя из соотношения сил, которое было учтено на основании предыдущих игр.

Вообще говоря, можно "вывести из турнира" игрока, находящегося в корне дерева, заменить его заведомо слабейшим новичком и повторить розыгрыш. Включение этого слабака приведет к тому, что первоначально второй по силе участник станет теперь наилучшим и именно он окажется в корне, если вновь вычислить победителей в верхних уровнях дерева. Для этого нужно из.менить лишь один путь в дереве, так что для выбора следующего по силе игрока необходимо менее [Ig iV] дополнительных сравнений. Суммарное время выполнения такой сортировки посредством выбора примерно пропорционально N log N, как и утверждалось выше.

На рис. 23 показано, как применить эту схему к нашим 16 числам. Заметим, что для того, чтобы знать, куда вставлять следующий элемент -оо, необходимо помнить, где находился ключ, оказавшийся в корне. Поэтому узлы разветвления в действительности содержат указатели или индексы, описывающие позицию ключа, а не сам ключ. Отсюда следует, что необходима память для N исходных записей, N -1 указателей и ЛГ выводимых записей. (Разумеется, если вывод идет на ленту или диск,, то не нужно сохранять выводимые записи в оперативной памяти.)

Чтобы Оценить те замечательные усовершенствования, которые мы собираемся обсудить, в этом месте рекомендуется прервать чтение и выполнить упр. 10. Не усвоив базовые принципы рассматриваемого метода, нельзя двигаться дальше.

Одна из модификаций выбора из дерева, введенная, по существу, К. Э. Айвер-соном (К. Е. Iverson) [А Programming Language (Wiley, 1962), 223-227], устраняет необходимость указателей. Достигается это тем, что мы "заглядываем вперед": когда победитель матча на нижнем уровне поднимается вверх, на нижнем уровне его сразу же можно заменить элементом -оо; когда же победитель перемещается вверх с одного разветвления на другое, его можно заменить игроком, который, в конце концов, все равно должен подняться на его прежнее место (а именно - наибольшим из двух ключей, расположенных под ним). Повторяя эту операцию как можно чаще, придем от рис. 23, (а) к рис. 24.

Коль скоро дерево построено таким образом, можно продолжать сортировку "нисходящим", а не "восходящим" методом, показанным на рис. 23: выводится

512 908 653 765

/\ /\ /\ /\

503 512 908 897 653 509 677 765

/\ /\ /\ /\ /\ /\ /\ /\ 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

(а) Исходная конфигурация

.897.

512 897 653 765

/\ /\ /\ /\

503 512 170 897 653 509 677 765

/\ /\ /\ /\ /\ /\ /\ /\

503 087 512 061 -оо 170 897 275 653 426 154 509 612 677 765 703

(Ь) Ключ 908 заменен значением -оо, а вторая по старшинству запись перемещается в корень

.512.

512 275 509 -оо

/\ /\ /\ /\

503 512 170 275 426 509 -оо -оо

/\ /\ /\ /\ /\ /\ /\ /\

503 087 512 061 -оо 170 -оо 275 -оо 426 154 509 -оо -оо -оо -оо

(с) Конфигурация после вывода 908, 897, 765, 703, 677, 653 и 612 Рис. 23. Пример сортировки посредством выбора.

.908.

512 275 653 703

/\ /\ /\ /\

503 061 170 -оо 426 509 677 -оо

/\ /\ /\ /\ /\ /\ /\ /\

-оо 087 -оо -оо -оо -оо -оо -оо -оо -оо 154 -оо 612 -оо -оо -оо

Рис. 24. Принцип Питера, примененный к сортировке. Каждый поднимается на свой уровень компетенции в иерархии.