3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ O(n log n)

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

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

Общий метод состоит в том, чтобы поставить в соответствие каждому листу дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям. Таким образом, можно определить среднее число сравнений, производимых данным алгоритмом сортировки, если вычислить сумму взятую по всем листьям дерева решений данного алгоритма, в которой вероятность достижения листа, его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4.

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

Доказательство. Обозначим через сумму глубин листьев двоичного дерева Пусть ее наименьшее значение, взятое по всем двоичным деревьям листьями. Покажем индукцией по что

Базис, т. е. случай тривиален. Допустим, что предположение индукции верно для всех значений меньших Рассмотрим дерево решений листьями. Оно состоит из корня с левым поддеревом листьями и правым поддеревом листьями при некотором Ясно, что

Поэтому наименьшее значение дается равенством

Учитывая предположение индукции, получаем отсюда

Легко показать, что этот минимум достигается при Следовательно,

Таким образом, для всех

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

Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сравнений для некоторой постоянной

Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией для некоторой постоянной с (как и у всякой сортировки с помощью сравнений), но составляет лишь часть

Рис. 3.7. Программа Быстрсорт.

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

Алгоритм 3.5. Быстрсорт

Вход. Последовательность из элементов

Выход. Элементы последовательности 5, расположенные по порядку.

Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове

Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из элементов за среднее время

Доказательство. Корректность алгоритма 3.5 доказывается прямой индукцией по длине последовательности Чтобы проще было анализировать время работы, допустим, что все элементы в различны. Это допущение максимизирует размеры последовательностей которые строятся в строке 3, и тем самым максимизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из элементов. Ясно, что для некоторой постоянной

Допустим, что элемент а, выбираемый в строке 2, является наименьшим элементом среди элементов последовательности Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время соответственно. Так как равновероятно принимает любое значение между 1 и и, а итоговое построение последовательности очевидно занимает

время для некоторой постоянной с, то

Алгебраические преобразования в (3.3) приводят к неравенству

Покажем, что при справедливо неравенство где Для базиса неравенство непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде

Так как функция вогнута, легко показать, что

Подставляя (3.6) в (3.5), получаем

Поскольку то Таким образом, неравенство следует из (3.7).

Рассмотрим две детали, важные для практической реализации алгоритма. Первая — способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого оператора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). Последовательность, к которой применяется подпрограмма сортировки, часто бывает уже "как-то" рассортирована, так что первый элемент мал с вероятностью выше средней. Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упорядоченной последовательности без повторений, а в качестве элемента а всегда выбирается первый элемент из в последовательности всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов.

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

Вторая деталь — как эффективно разбить на три последовательности Можно (и желательно) иметь в массиве все исходных элементов. Так как процедура БЫСТРСОРТ вызывает себя рекурсивно, ее аргумент всегда будет находиться в последовательных компонентах массива, скажем для некоторых и Выбрав "произвольный" элемент а, можно устроить разбиение последовательности на этом же месте. Иными словами, можно расположить в компонентах при некотором Затем можно, если нужно, расщепить но обычно эффективнее просто рекурсивно вызвать БЫСТРСОРТ на если оба этих множества не пусты.

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

Рис. 3.8. Разбиение на на месте их расположения.

и все время в будут находиться элементы из Аналогично вначале все время будут находиться элементы из Это разбиение производит подпрограмма на рис. 3.8.

Затем можно вызвать БЫСТРСОРТ для массива т. е. и для массива т. е. Но если (и тогда то надо сначала удалить из хотя бы один элемент, равный а. Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последовательностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива.

Пример 3.5. Разобьем массив

по элементу -оператор (строка 4) уменьшает с 9 до 7, поскольку числа оба не меньше а, но Строка 5 не увеличивает с его начального значения 1, поскольку Поэтому мы переставляем полагаем и получаем массив на рис. 3.9, а. Результаты, получаемые после следующих двух срабатываний цикла в строках 3—9, показаны на рис. В этот момент и выполнение while-оператора, стоящего в строке 3, заканчивается.

Рис. 3.9. Разбиение массива.