2.8.1 Описание алгоритма

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

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

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

Рисунок 2.10 – Работа алгоритма Bucket-Sort

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

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