Стр. 84 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
82
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Рассмотрим противоположный случай, когда ГЭ оказался наибольшим или
наименьшим, т.е. одна подгруппа пустая, а во второй на 1 элемент меньше, чем
в исходной.
T
(
n
) =
O
(
n
) +
T
(0) +
T
(
n
-1) =
O
(
n
) +
T
(
n
-1). (
T
(0)=0) .
Пусть во всех поколениях массив разделяется также асимметрично.
Тогда
T
(
n
) =
O
(
n
) +
О
(
n
-1) +
T
(
n
-2) =
O
(
n
) +
O
(
n
-1) +
O
(
n
-2) + … +
O
(1) =
O
(
n
2
).
Таким образом, в худшем случае быстрая сортировка работает медленнее,
чем любой другой тривиальный алгоритм, за счет потерь на выбор ГЭ,
организации рекурсии и т.д.
В среднем случае производительность
QuickSort
– 2
n
log
2
n
. – это лучший
результат среди всех методов сортировки.
Однако от быстрой сортировки приходится отказываться в тех задачах, где
число операций строго ограничено по времени сверху.
Для практической реализации быстрая сортировка нуждается в следующем
усовершенствовании.
Когда число элементов в текущем подмассиве оказывается меньше
некоторого порога, расходы на деление и другие операции быстрой сортировки
становятся настолько чувствительными, что быстрая сортировка на этом
подмассиве работает медленно. Следовательно, как только в подмассиве
разница между
i
и
j
стала меньше порога, целесообразно для сортировки
текущего подмассива использовать любой другой алгоритм, например вставку.
Значение порога колеблется от 9 до 16 элементов.
Окончательный вариант быстрой сортировки:
QuickSort(x, i, j)
{
if (i>=j) return;
if ((j-i)<порог)
{
Вставка(x, i, j);
return;
}
S = <выбор главного элемента>
<x
1
меняем с x
s
>
Separate(x, i, j, s);
<x
i
меняем с x
s
>
if ((s-
1
-i)<(j-(s+
1
)))
{
