9.3-2 Какие из следующих алгоритмов сортировки являются устойчивыми: сортировка вставками, сортировка слиянием, сортировка с помощью кучи, быстрая сортировка? Объясните, каким способом можно любой алгоритм сортировки превратить в устойчивый. Сколько при этом потребуется дополнительного времени и памяти?

9.3-3 Докажите по индукции, что алгоритм цифровой сортировки правилен. Где в вашем доказательстве используется устойчивость алгоритма сортировки цифр?

9.3-4 Объясните, как рассортировать га целых положительных чисел, не превосходящих га2, за время О (га).

9.3-5* Пусть мы сортируем перфокарты с помощью сортировочной машины, начиная со старшего разряда. Сколько раз придётся запустить машину (в худшем случае) для сортировки d-значных чисел? Какое максимальное количество стопок карт придётся одновременно хранить по ходу дела?

9.4. Сортировка вычерпыванием

Алгоритм сортировки вычерпыванием (bucket sort) работает за линейное (среднее) время. Как и сортировка подсчётом, сортировка вычерпыванием годится не для любых исходных данных: говоря о линейном среднем времени, мы предполагаем, что на вход подаётся последовательность независимых случайных чисел, равномерно распределённых на промежутке [0; 1) (определение равномерного распределения дано в разд. 6.2).

[Заметим, что этот алгоритм - детерминированный (не использует генератора случайных чисел); понятие случайности возникает лишь при анализе времени его работы.]

Идея алгоритма состоит в том, что промежуток [0; 1) делится на га равных частей, после чего для чисел из каждой части выделяется свой ящик-черпак (bucket), и га подлежащих сортировке чисел раскладываются по этим ящикам. Поскольку числа равномерно распределены на отрезке [0;1), следует ожидать, что в каждом ящике их будет немного. Теперь отсортируем числа в каждом ящике по отдельности и пройдёмся по ящикам в порядке возрастания, выписывая попавшие в каждый из них числа также в порядке возрастания.

Будем считать, что на вход подается га-элементный массив А, причем 0 А[г] < 1 для всех г. Используется также вспомогательный массив В[0 . .га - 1], состоящий из списков, соответствующих ящикам. Алгоритм использует операции со списками, которые опи-

Рис. 9.4 Работа алгоритма Bucket-Sort, (а) На вход подан массив А[1. . 10]. (б) Массив списков В[0. . 9] после выполнения строки 5. Список с индексом г содержит числа, у которых первый знак после запятой есть г. Отсортированный массив получится, если последовательно выписать списки В[0],. . . , В[9].

6 соединить списки В[0], В[1],..., В[п - 1] (в указанном порядке)

На рис. 9.4 показана работа этого алгоритма на примере массива из 10 чисел.

Чтобы показать, что алгоритм сортировки вычерпыванием правилен, рассмотрим два числа A[i] и A[j]. Если они попали в разные ящики, то меньшее из них попало в ящик с меньшим номером, и в выходной последовательности оно окажется раньше; если они попали в один ящик, то после сортировки содержимого ящика меньшее число будет также предшествовать большему.

Проанализируем время работы алгоритма. Операции во всех строках, кроме пятой, требуют (общего) времени 0{п). Просмотр всех ящиков также занимает время 0{п). Таким образом, нам остаётся только оценить время сортировки вставками внутри ящиков.

Пусть в ящик B[i] попало гц чисел {гц - случайная величина). Поскольку сортировка вставками работает за квадратичное время, математическое ожидание длительности сортировки чисел в ящике номер г есть 0(М[га2]), а математическое ожидание суммарного

саны в разд. 11.2.

3do добавить A[i] к списку -B[LraWJ]

4for г +- 0 to п - 1

5do отсортировать список В\г\ (сорт!

Глава 9 Сортировка за линейное время времени сортировки во всех ящиках есть

п - 1/п-1

J]0(M[ra2])=0 £М[п?]

(9.1)

8 = 0V 8 = 0

Найдём функцию распределения случайных величин гц. Поскольку числа распределены равномерно, а величины всех отрезков равны, вероятность того, что данное число попадет в ящик номер г, равна 1/га. Стало быть, мы находимся в ситуации примера из разд. 6.6.2 с шарами и урнами: у нас га шаров-чисел, га урн-ящиков, и вероятность попадания данного шара в данную урну равна р = 1/га. Поэтому числа гц распределены биномально: вероятность того, что гц = к, равна Скрк(1 - р)п~к, математическое ожидание равно М[гаг] = пр = 1, и дисперсия равна D[ra8] = гар(1- р) = 1 - 1/га. Из формулы (6.30) имеем:

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

Упражнения

9.4-1 Следуя образцу рис. 9.4, покажите, как работает алгоритм Bucket-Sort для массива А = (0.79,0.13,0.16,0.64,0.39, 0.20,0.89,0.53,0.71,0.42).

9.4-2 Каково время работы алгоритма сортировки вычерпыванием в худшем случае? Придумайте его простую модификацию, сохраняющую линейное среднее время работы и снижающую время работы в худшем случае до О (га lgra).

9.4-3* Дано га независимых случайных точек с координатами (жг;уг), равномерно распределённых в круге радиуса 1 с центром в начале координат (это означает, что вероятность найти точку в какой-то области пропорциональна площади этой области). Разработайте алгоритм, располагающий точки в порядке возрастания расстояния от центра и имеющий среднее время работы в (га). (Указание: воспользуйтесь сортировкой вычерпыванием, но позаботьтесь о том, чтобы площади ящиков были равны).

M[ra2] = D[ra8] + M2[ra8] = 2

1

6(1).

га

9.4-4* Пусть X - случайная величина. Ее функция распределения

(probability distribution function) определяется формулой Р(х) =