в примере (е) мы имеем дерево

Его составные элементы и представляют собой ключ к обращению алгоритма Р.]

40. [НМ4З] Предположим, что некоторая диаграмма Юнга построена путем последовательного размещения чисел 1, 2, ..., п таким способом, что выбор очередной доступной ячейки для каждого следующего числа равновероятен. Например, с вероятностью 5 • iljIilliililTaK будет получена диаграмма (1).

Докажите, что с большой вероятностью результирующая форма (ni, П2,..., Пт) будет иметь т и л/бп и л/к + y/rvk+x ~ у/т при О < А: < т.

41. [25] (Беспорядок в библиотеке.) Некоторые бестолковые читатели часто возвращают книги в библиотеку и ставят их на полки где попало. Измерить вносимый при этом беспорядок можно, рассмотрев минимальное количество повторений простейшей процедуры перемещения данной книги, которое необходимо для того, чтобы все книги заняли надлежащие им места.

Пусть 7г = oi 02 ... а„ - перестановка множества {1,2,..., п}. Операция удаления-вставки превращает ж в

oi ... Oi i o,+i ...Uj ai Oj+i ...an или oi ... Oj o; Uj+i ... o, i Oi+i ... o„

для некоторых i и j. Пусть dis(7r) - минимальное число операций удаления-вставки, которое рассортирует ж и приведет его в порядок. Можно ли выразить dis(7r) в терминах простых характеристик ж?

► 42. [30] (Беспорядок генов.) Молекула ДНК растения Lobelia fervens имеет гены в последовательности дтдхдгЯАЯъдздв 1 где д обозначает отражение слева направо дт. Те же самые гены существуют и в табаке, но в порядке дхдгдзддбдвдг. Покажите, что для того, чтобы получить из д\д2дъдАдъдбд7 последовательность ддхдгдАдъдздв, необходимо пять операций "перебрасывания" подцепочек. (Операция перебрасывания превращает afif в а/37, если Q, /3 и 7 являются цепочками.)

43. [35] Продолжая предыдущее упражнение, покажите, что по крайней мере п+1 операций перебрасывания необходимо для сортировки любого варианта компоновки gig2 дп. Постройте примеры, которые требуют п+1 операций для всех п > 3.

44. [М37] Покажите, что среднее число перебрасываний, необходимых для сортировки случайной компоновки п генов, больше, чем п - Нп, если все 2" п! компоновок генов равновероятны.

5.2. ВНУТРЕННЯЯ СОРТИРОВКА

Начнем обсуждение "хорошего" процесса сортировки с маленького эксперимента. Как бы вы решили следующую задачу программирования?

"В ячейках памяти R+1, R+2, R+3, R+4 и R+5 содержится пять чисел. Напишите программу, которая переразмещает, если нужно, эти числа так, чтобы они расположились в порядке возрастания."

(Если вы уже знакомы с какими-либо методами сортировки, постарайтесь, пожалуйста, на минуту забыть о них; вообразите, что вы решаете такую задачу впервые, не имея никакого представления о том, как к ней подступиться.)

Прежде чем читать дальше, настоятельно просим вас найти хоть какое-нибудь решение этой задачи.

Время, затраченное на решение приведенной выше задачи, окупится с лихвой, когда вы продолжите чтение этой главы. Возможно, ваше решение окажется одним из следующих.

A. Сортировка методом вставок. Элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. (Именно таким способом игроки в бридж упорядочивают свои карты, беря по одной.)

B. Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены.

C. Сортировка посредством выбора. Сначала выделяется наименьший (или, быть может, наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся и т. д.

D. Сортировка путем подсчета. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется после подсчета числа меньших ключей.

E. Специальная сортировка. Она хороша для пяти элементов, указанных в задаче, но не поддается простому обобщению, если элементов больше.

F. Способ лентяя. Вы не откликнулись на наше предложение и отказались решать задачу. Жаль - вы упустили свой шанс... Если вы дошли до этого места, то и так уже слишком много знаете.

G. Новая суперметодика сортировки. Это существенно усовершенствованные известные методы. (Если вы нашли такую методику, пожалуйста, немедленно сообщите об этом автору.)

Если бы данная задача была сформулирована, скажем, для 1 ООО элементов, а не для 5, то вы могли бы открыть и более тонкие методы, о которых речь пойдет ниже. В любом случае, приступая к новой задаче, разумно найти какую-нибудь очевидную процедуру, а затем попытаться улучшить ее. Развитие вариантов А, В и С приводит к появлению важных классов методов сортировки, которые представляют собой усовершенствованные сформулированные выше простые идеи.

Было изобретено множество различных алгоритмов сортировки, и в этой книге рассматривается около 25 из них. Такое пугающее количество методов на самом

деле - лишь малая толика всех алгоритмов, придуманных на сегодняшний день; многие уже устаревшие методы мы вовсе не будем рассматривать или упомянем лишь вскользь. Почему же существует так много методов сортировки? Применительно к программированию это частный случай вопроса "Почему существует так много методов хТ] где х пробегает множество всех задач. Ответ если и неочевиден, то вполне понятен - каждый метод имеет свои преимущества и недостатки, поэтому он оказывается эффективнее других при некоторых конфигурациях данных и аппаратуры. К сожалению, неизвестен наилучший способ сортировки (если он вообще существует); имеется много наилучших методов, но только в случаях, когда известно, что сортируется, на каком компьютере и с какой целью. Говоря словами Редьярда Киплинга, "существует 9 и еще 60 способов сложить песню племени, и каждый из них в отдельности хорош". Полезно изучить характеристики каждого метода сортировки, чтобы для конкретного случая можно было сделать разумный выбор. К счастью, эта задача не столь уж громоздка, поскольку алгоритмы взаимосвязаны подчас самым причудливым способом.

В начале этой главы мы ввели основную терминологию и обозначения, которые и будем использовать при изучении сортировки. Записи

Ri,R2,...,Rn (1)

должны быть рассортированы в порядке неубывания своих ключей Ki, К2, , К, т. е., по существу, нужно найти перестановку р(1)р(2).. .p{N), такую, что

P(i)<p(2)<---<p(;v). (2)

В этом разделе рассматривается внутренняя сортировка, когда число записей, подлежащих сортировке, достаточно мало, так что весь процесс можно провести в оперативной памяти компьютера, обладающей высоким быстродействием.

В одних случаях может понадобиться физически переставлять записи в памяти так, чтобы их ключи были упорядочены; в других можно обойтись вспомогательной таблицей некоторого вида, определяющей перестановку. Если записи и/или ключи занимают несколько слов памяти, то часто лучше составить новую таблицу адресных ссылок, которые указывают на записи, и работать с этими ссылками, не перемещая громоздкие записи. Такой метод называется сортировкой таблицы адресов (рис. 6). Если ключи короткие, а сопутствующая информация в записях велика, то для повышения скорости ключи можно вынести в таблицу адресных ссылок. Этот процесс называется сортировкой ключей.

В других схемах сортировки используется вспомогательное поле связи, которое включается в каждую запись. Связи обрабатываются таким образом, что в результате все они оказываются объединенными в линейный список, в котором каждая связь указывает на следующую по порядку запись. Этот способ называется сортировкой списка (рис. 7).

После сортировки таблицы адресов или списка можно по желанию расположить записи в порядке неубывания. Сделать это можно несколькими способами, требующими дополнительной памяти для хранения всего одной записи (см. упр. 10 и 12); или же можно просто переместить записи в новую область памяти, если она способна вместить все эти записи. Последний способ обычно вдвое быстрее первого, но требует почти в два раза больше памяти. Во многих приложениях вовсе не