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

Таблица 7.2. Эмпирическое исследование вариантов быстрой сортировки

В этой таблице представлена относительная стоимость нескольких различных вариантов быстрой сортировки на примере упорядочения первых N слов из книги Moby Dick. Непосредственное использование метода вставки для сортировки небольших подфайлов или игнорирование небольших подфайлов с последующей сортировкой того же файла методом вставки потом - суть стратегии, обеспечивающие один и тот же уровень эффективности, но в то же время экономия расходов, достигаемая за счет реализации обоих стратегий несколько ниже, чем для целочисленных ключей (см. табл. 7.1), поскольку стоимость операции сравнения строк влечет большие издержки. Если во время разбиения файлов просмотр не останавливается на дублированных ключах, то время сортировки файла, у которого все ключи одинаковы, подчиняется квадратичной зависимости; низкая эффективность проявляется в этом примере в связи с тем, что существует множество слов, которые встречаются в данных довольно часто. По той же причине разделение на три части обеспечивает высокий уровень эффективности сортировки; она на 30-35 процентов быстрее системной сортировки.

N У1 \ М Q X Т

12500 8 7 6 10 7 6

25000 16 14 13 20 17 12

50000 37 31 31 45 41 29

100000 91 78 76 103 113 68

Обозначения:

V Быстрая сортировка (программа 7.1).

I Сортировка вставками для подфайлов небольших размеров.

М Файлы небольших размеров игнорируются, завершающая сортировка вставками.

Q Системная сортировка qsort.

X Пропускаются дублированные ключи (квадратичная зависимость в случае, когда все ключи одинаковы).

Т Разделение на три части (программа 7.5).

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

Упражнения

7.39. Рассмотреть возможность усовершенствования сортировки выбором, вставками, пузырьковой сортировки и шейкер-сортировки применительно к строкам.

о 7.40. Сколько символов проверяются в рамках стандартного алгоритма быстрой сортировки (профамма 7.1, использующая строковый тип из профаммы 6.11) при сортировке файла, состоящего из строк длиной t, при этом все строки одинаковы? Дать ответ на тот же вопрос применительно к модификации, предложенной в тексте.

7.8. Выборка

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

Операция нахождения медианы представляет собой частный случай операции выборки {selection): нахождения к-то наименьшего числа в заданном наборе чисел. Поскольку сам алгоритм не может дать гарантии, что конкретный элемент - суть Аг-й наименьший, если не проверит и не распознает к - 1 элементов, которые меньше к, к N- к элементов, которые больше к, большая часть алгоритмов может возвратить все к наименьших элементов исходного файла без каких-либо дополнительных вычислений.

Операция выборки часто применяется при обработке экспериментальных и других видов данных. Широко практикуется использование медианы и других показателей порядковой статистики {order statistics) для деления файла на меньшие части. Нередко для дальнейшей обработки запоминается только некоторая часть большого файла; в таких случаях профамма, способная выбрать, скажем, 10 процентов наибольших элементов файла, может оказаться предпочтительнее, чем сортировка в полном объеме. Другим важным примером можно считать использование разделения вокруг медианы в качестве первой стадии многих алгоритмов типа разделяй и властвуй .

Мы уже рассматривали алгоритм, который может быть приспособлен непосредственно для выборки. Если к исключительно мало, то сортировка выбором (см. главу 6) будет работать хорошо, требуя для своего выполнения время, пропорциональное N к: сначала находим первый наименьший элемент, затем второй наименьший, равный наименьшему из оставшихся элементов после первого выбора, и так далее. Для несколько большего к мы найдем описание методов в главе 9, эти методы можно насфоить таким образом, что время их выполнения окажется пропорциональным logA:.

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

переупорядочивает массив а[1],...,а[г] и возвращает целое i такое, что элементы от а[1] до a[i-1] меньше или равны a[i], а элементы от a[i+l] до а[г] больше или равны a[i]. Если к равно i, то задача решена. С другой стороны, если к < 1, следует продолжать работу на левом подфайле; если к > i, работу необходимо продолжать на правом подфайле. Подобный подход прямо выводит на рекурсивную программу выборки, каковой является программа 7.6. Пример работы этой процедуры на файле небольших размеров показан на рис. 7.13.

Программа 7.6. Выборка

Данная процедура производит разделение массива относительно (к-1)-го наименьшего элемента (элемент в а[к]): она переупорядочивает массив таким образом, что а[1],...,а[к-1] меньше или равны а[к], а а[к+1].....а[г] больше или равны а[к].

Например, можно вызвать elect(a,О,N-1,N/2) с

целью разделения массива по значению медианы, оставляя медиану в a[N/2].

template <class Item> void select (Item a[], int 1, int r, int k)

if (r <= 1) return;

int i = partition (a, 1, r) ;

if (i > k) select(a, 1, i-1,

if (i < k) select(a, i+1, r.

ASORT I NGEXAMPLE A A E©T I NGOXSMPLR L i N G о P M(r)X T S

L I G®0 P N ,i\M-0iy AAEELIGnOPNRXTS

РИСУНОК 7.13. ВЫБОРКА МЕДИАНЫ

Чтобы найти медиану из ключей, в рассматриваемом примере сортировка, использующая метод разделения, выполняет три рекурсивных вызова. Во время первого вызова отыскивается восьмое наименьшее число в файле из 15 элементов, в то время как разделение позволяет получить четвертое наименьшее (Е); во втором вызове ищется четвертое наименьшее число в файле из И элементов и разделение дает восьмое наименьшее (R), далее, в третьем вызове ищется четвертое наименьшее число в файле размером 7, которым будет (М). Файл переупорядочен теперь таким образом, что медиана занимает окончательное место, элементы, меньшие медианы по значению, сосредоточен(>1 слева от нее, элементы, большие нее по значению - справа от нее (элементы, равные медиане, могут быть помещены с любой ее стороны), однако окончательный порядок в файле еще не установлен.

к) ; к);

Программа 7.7. Нерекурсивная выборка

Нерекурсивная реализация выборки просто строит раздел, затем помещает левый указатель в раздел, если этот раздел оказывается слева от искомой позиции, или помещает правый указатель в раздел, если раздел оказывается справа от искомой позиции.

template <class Item>

void select(Item a[] , int 1, int r, int k)

while (r > 1) { int i = partition (a, 1, r) ; if (i >= k) r = i-1; if (i <= k) 1 = i+1;