проста: массив делится на четыре участка (перечисляем их слева направо): меньшие границы, равные границе, непросмотренные и большие границы.]

Упражнения

8.4-1 Докажите, что наименьшее время работы быстрой сортировки составляет Q(гаlgra).

8.4-2 Докажите, что функция q2 + (га - q)2 на отрезке [1,га - 1] принимает наибольшее значение в концах отрезка.

8.4-3 Докажите, что математическое ожидание времени работы процедуры Randomized-Quicksort на любом входе есть fi(ralgra).

8.4-4 На практике время работы быстрой сортировки можно уменьшить, если на завершающем этапе (когда массив почти отсортирован) использовать сортировку вставками. Сделать это можно, например, так: пусть процедура Randomized-Quicksort(A,p, г) ничего не делает, если r-p+1 < к (т.е. сортируемый массив содержит меньше к элементов). После окончания рекурсивных вызовов получившийся массив сортируется с помощью сортировки вставками. Докажите, что математическое ожидание времени работы такого алгоритма составляет 0(пк + ralg(ra/A;)). Как бы вы стали выбирать число к?

8.4-5* Докажите равенство

/ х In х ах = -х In ж--х

J24

Выведите отсюда (используя метод сравнения с интегралом) более сильную (в сравнении с (8.5)) оценку для суммы Xfc=i klgk.

8.4-6* Рассмотрим следующую модификацию процедуры Randomized-Partition: случайным образом выбираются три элемента массива и в качестве граничного элемента берётся средний по величине из выбранных трёх камней. Оцените вероятность того, что при этом разбиение будет сбалансировано не хуже, чем а : 1 - а.

Задачи

8-1 Правильность процедуры разбиения

Покажите, что процедура Partition работает правильно. Для этого докажите следующее:

Задачи к главе 8

169

а.В процессе работы процедуры индексы г и j не выходят за пределы отрезка [р. .г].

б.В момент окончания работы процедуры индекс j не может быть равен г (т.е. обе части разбиения непусты).

в.В момент окончания работы процедуры любой элемент массива А\р. .j] не больше любого элемента массива A[j + 1.. г].

8-2 Алгоритм Ломуто для разбиения

Вариант процедуры Partition, который мы сейчас рассмотрим, принадлежит Н. Ломуто (N. Lomuto). В процессе работы строятся куски А\р. л] и А [г + 1. .j], причём элементы первого куска не больше х = А[г], а элементы второго куска - больше х.

Lomuto-Partition(A, р, г)

1х +- А[г]

2г <т- р - 1

3for j f- р to г

4do if A[j] x

5then ibt + l

6поменять А [г] f-> A[j]

7if г < r

8then return i

9else return г - 1

а.Докажите, что процедура Lomuto-Partition работает правильно.

б.Сколько раз процедуры Partition и Lomuto-Partition могут перемещать один и тот же элемент? (Укажите наибольшие значения.)

в.Докажите, что процедура Lomuto-Partition, как и процедура Partition, требует времени в (га), где га - число элементов в массиве.

г.Заменим в тексте процедуры Quicksort процедуру Partition на Lomuto-Partition. Как изменится время быстрой сортировки для массива, все элементы которого равны?

д.Рассмотрим процедуру Randomized-Lomuto-Partition, которая меняет А [г] со случайно выбранным элементом массива и затем вызывает процедуру Lomuto-Partition. Докажите, что вероятность того, что процедура Randomized-Lomuto-Partition вернёт значение q, равна вероятности того, что процедура Randomized-Partition вернёт значение р + г - q.

8-3 Сортировка по частям

Профессор предложил следующий «продвинутый» алгоритм сортировки:

Stooge-Sort(A,

1if А[г] > A[j]

2then поменять A[i] f-> A[j]

3if i + 1 j

4then return

5&- * + 1)/3J> Округление с недостатком.

6Stooge-Sort(A, г, j - k) > Первые две трети.

7Stooge-Sort(A, г + k, j) о Последние две трети.

8Stooge-Sort(A, i, j - к) > Опять первые две трети.

а.Докажите, что процедура Stooge-Sort действительно сортирует массив.

б.Найдите рекуррентное соотношение для наибольшего времени работы процедуры Stooge-Sort и получите из него оценку этого времени.

в.Сравните наибольшее время работы процедуры Stooge-Sort с наибольшим временем для других вариантов сортировки (вставками, слиянием, с помощью кучи и быстрой сортировки). Стоит ли продлевать контракт с профессором?

8-4 Размер стека при быстрой сортировке

Процедура Quicksort два раза рекурсивно вызывает себя (для левой и для правой части). В действительности без второго рекурсивного вызова можно обойтись, заменив его циклом (именно так хорошие компиляторы обрабатывают ситуацию, когда последним оператором процедуры является рекурсивный вызов; для такой ситуации есть термин tail recursion):

Quicksort, р, г)

1while р < г

2do > Разбить и отсортировать левую часть.

3q <- Partition (А, р, г)

4Quicksort, р, q)

5р <- q + 1

а.Докажите, что процедура Quicksort действительно сортирует массив.

Как правило, компиляторы реализуют рекурсию с помощью стека, где хранятся копии локальных переменных для каждого рекурсивного вызова. Вершина стека содержит информацию, относящуюся к текущему вызову; когда он завершается, информация удаляется из стека. В нашем случае для каждого рекурсивного вызова локальные переменные занимают объём 0(1), так что необходимый размер стека (stack depth) пропорционален глубине рекурсии.

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