Программа 7.7 представляет собой нерекурсивную версию, построенную на базе рекурсивной версии, представленной в программе 7.6. Поскольку эта профамма всегда завершается рекурсивным вызовом самой себя, мы просто восстанавливаем начальные значения параметров и возвращаемся в начало профаммы. Это значит, что мы отказываемся от рекурсии и не используем стек, а также исключаем из программы вычисления, в которых используется к, и рассматриваем к только как индекс массива.

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

Как и в случае быстрой сортировки, можно предположить (в первом приближении), что в случае файла очень больших размеров каждое разделение разбивает файл напополам, при этом для выполнения процесса разделения фебуется выполнить Л + N/2 + N/4 + N/S +... = 2N операций сравнения. Но поскольку разделение выполняется именно для быстрой сортировки, это грубое приближение недалеко от истины. Анализ, подобный приводимому в разделе 7.2 анализу быстрой сортировки, но гораздо более сложный (см. раздел ссылок), дает результаты, согласно которым среднее число сравнений определяется выражением

2N + 2к\п( N/k) + 2(N- к) 1п( N/(N- к)),

которое линейно зависит от любого допустимого значения к. Вычисление этой формулы при к = N / 2 показывает, что для нахождения медианы необходимо выполнить ( 2 + 2 1п 2 ) Л сравнений.

Пример того, как этот метод находит медиану в крупном файле, представлен на рис. 7.14. В рассматриваемом случае имеется только один подфайл, который при каждом вызове уменьшается в размере в одно и то же число раз, таким образом, эта процедура завершается за О (log Л) шагов. Выполнение программы можно ускорить, введя в нее выборку, однако при этом следует соблюдать осторожность (см. упражнение 7.45.

РИСУНОК 7.14. ВЫБОР МЕДИАНЫ С ПОМОЩЬЮ ПРОЦЕДУРЫ РАЗДЕЛЕНИЯ.

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

ишшт

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

Упражнения

7.41. Сколько в среднем потребуется операций сравнения, чтобы найти наименьший элемент в файле из N элементов, применяя для этой цели процедуру select?

7.42. Сколько в среднем потребуется операций сравнения, чтобы найти аЛ-й наименьший элемент, применяя для этой цели процедуру select, для а = 0.1, 0.2, ...,0.9?

7.43. Сколько потребуется операций сравнения в наихудшем случае, чтобы найти медиану из N элементов, применяя для этой цели процедуру select?

7.44. Напишите эффективную программу переупорядочения файла таким образом, чтобы все элементы с ключами, равными медиане, оказались в окончательной позиции, элементы меньше медианы - слева и элементы больше медианы - справа.

7.45. Проведите исследование идеи использования выборки с целью повышения эффективности выбора. Совет: Использование медианы не всегда приводит к ожидаемым результатам.

7.46. Реализовать алгоритм выборки на базе метода трехпутевого разделения на примере крупного файла с ключами, принимающими t различных значений, для г = 2, 5 и 10.

Слияние и

сортировка

слиянием

Семейство алгоритмов быстрой сортировки, рассмотренное в главе 7, основано на операции выборки: нахождение к-то минимальносо элемента в файле. Мы убедились в том, что выполнение операции выборки аналогично делению файла на две части, на часть, содержащую все к наименьших элементов, и часть, содержащую N- к больших по значению элементов. В этой главе исследуется семейство алгоритмов сортировки, в основе которых лежит вспомогательный процесс, известный как слияние, т.е., объединение двух отсортированных файлов в один файл большего размера. Слияние является основой для простого алгоритма сортировки типа разделяй и властвуй (см. раздел 5.2), а также для его двойника - алгоритма восходящей (снизу-вверх) сортировки слиянием, при этом оба из них достаточно просто реализуются.

Выборка и слияние - суть вспомогательные операции в том смысле, что выборка разбивает файл на два независимых файла, в то время как слияние объединяет два независимых файла в один. Контраст между этими двумя операциями становится очевидным, если применить принцип разделяй и властвуй для создания конкретных методов сортировки. Можно изменить организацию файла таким образом, 4to когда обе части файла подвергаются сортировке, упорядочивается и весь файл; и наоборот, можно разбить файл на две части для последующей сортировки, а затем объединить упорядоченные части, чтобы получить весь файл в упорядоченном виде. Мы уже видели, что получается в первом случае: это ни что иное как быстрая сортировка, которая состоит из процедуры выборки, за которой следуют два рекурсивных вызова.