Стр. 83 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
81
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
r
1
r
0
а начальный и конечный индекс правого подмассива сохраняется в стеке.
Пусть аналогичная ситуация возникает в каждом последующем поколении.
Qsort(1,
n
)
Qsort(
n,n
)
Qsort(1,
n
-2)
Qsort(
n
-2,
n
-2)
Qsort(1,
n
-4)
в стек
в стек
………
Очевидно, что если эта ситуация повторится в всех поколениях, то глубина
рекурсии или стека составит
n
/2.
Таким образом, рекурсивно необходимо сортировать меньший из двух
подмассивов.
Анализ быстродействия.
Общее число операций на быструю сортировку массива, состоящего из
n
элементов:
T
(
n
) =
O
(
n
) +
T
(
s
-1) +
T
(
n
-
s
),
эти затраты складываются из:
1)
O
(
n
) – затрат на разделение исходного массива и на сортировку;
2)
T
(
s
-1) +
T
(
n
-
s
) – 1-й и 2-й подмассивов.
s
– позиция, где оказался главный элемент после сортировки.
Пусть каждый раз в результате деления текущий подмассив делится
пополам.
Тогда
T
(
n
) =
O
(
n
) + 2
T
(
n
/2).
Решением этого рекуррентного уравнения будет
O
(
n
log
2
n
). Это лучший
результат среди всех известных методов сортировки.
