Быстрая сортировка Хоара

В заключение приведем рекурсивный алгоритм сортировки массива, который на практике является одним из самых быстрых. Пусть дан массив ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}$ . Рекурсивная процедура sort(l,r:integer) сортирует участок массива с индексами из полуинтервала $({\hbox{\tt l}},{\hbox{\tt r}}]$ ,то есть ${\hbox{\tt a[l+1]}}\ldots{\hbox{\tt a[r]}}$ ,не затрагивая остального массива.

    procedure sort (l,r: integer);
    begin
    | if (l = r) then begin
    | | ничего делать не надо - участок пуст
    | end else begin
    | | выбрать случайное число s в полуинтервале (l,r]
    | | b := a[s]
    | | переставить элементы сортируемого участка так, чтобы
    | |   сначала шли элементы, меньшие b - участок (l,ll]
    | |   затем элементы, равные b        - участок (ll,rr]
    | |   затем элементы, большие b       - участок (rr,r]
    | | sort (l,ll);
    | | sort (rr,r);
    | end;
    end;

Разделение элементов сортируемого участка на три категории (меньшие, равные, больше) рассматривалась в главе 1, здесь (это можно сделать за время, пропорциональное длине участка). Конечность глубины рекурсии гарантируется тем, что длина сортируемого участка на каждом уровне рекурсии уменьшается хотя бы на 1 .

$\scriptstyle{\blacktriangleright}$ 7.4.7. (Для знакомых с основами теории вероятностей). Доказать, что математическое ожидание числа операций при работе этого алгоритма не превосходит $Cn\log n$ , причем константа C не зависит от сортируемого массива.

[Указание. Пусть T(n) -- максимум математического ожидания числа операций для всех входов длины n . Из текста процедуры вытекает такое неравенство: $\begin{displaymath} T(n) \leqslant Cn + \frac{1}{n}\sum_{k+l=n-1} \bigl( T(k)+T(l) \bigr)\end{displaymath}$ Первый член соответствует распределению элементов на меньшие, равные и большие. Второй член -- это среднее математическое ожидание для всех вариантов случайного выбора. (Строго говоря, поскольку среди элементов могут быть равные, в правой части вместо T(k) и T(l) должны стоять максимумы T(x) по всем x , не превосходящим k или l , но это не мешает дальнейшим рассуждениям.) Далее индукцией по n нужно доказывать оценку $T(n) \leqslant C'n\ln n$ .При этом для вычисления среднего значения $x\ln x$ по всем $x=1,\ldots,n-1$ нужно вычислять $\int_1^n x \ln x dx$ по частям как $\int \ln x \, d(x^2)$ .При достаточно большом C' член Cn в правой части перевешивается за счет интеграла $\int x^2\, d\ln x$ , и индуктивный шаг проходит.] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 7.4.8. Имеется массив из n различных целых чисел и число k . Требуется найти k -ое по величине число в этом массиве, сделав не более Cn действий, где C -- некоторая константа, не зависящая от k и n .

Замечание. Сортировка позволяет очевидным образом сделать это за $Cn\log n$ действий. Очевидный способ: найти наименьший элемент, затем найти второй, затем третий,..., k -ый требует порядка kn действий, то есть не годится (константа при n зависит от k ).

[Указание. Изящный (хотя практически и бесполезный -- константы слишком велики) способ сделать это таков:

А. Разобьем наш массив на n/5 групп, в каждой из которых по 5 элементов. Каждую группу упорядочим.

Б. Рассмотрим средние элементы всех групп и перепишем их в массив из n/5 элементов. С помощью рекурсивного вызова найдем cредний по величине элемент этого массива.

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

Г. Применим рекурсивно наш алгоритм к выбранной части.

Пусть T(n) -- максимально возможное число действий, если этот способ применять к массивам из не более чем n элементов (k может быть каким угодно). Имеем оценку: $\begin{displaymath} T(n) \leqslant Cn + T(n/5) + T (\hbox{\rm примерно}\ 0{,}7n).\end{displaymath}$ Последнее слагаемое объясняется так: при разбиении на части каждая часть содержит не менее 0,3n элементов. В самом деле, если x -- средний из средних, то примерно половина всех средних меньше x . А если в пятерке средний элемент меньше x , то еще два заведомо меньше x . Тем самым по крайней мере 3/5 от половины элементов меньше x .

Теперь по индукции можно доказать оценку $T(n) \leqslant Cn$ (решающую роль при этом играет то обстоятельство, что ). ] $\blacktriangleleft$

pvv
1/8/1999