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

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

Алгоритм сортировки вычерпыванием (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 ]Если они попали в разные ящики, то меньшее из них попало в ящик с меньшим номером, и в выходной последовательности оно окажется раньше, если они попали в один ящик, то после сортировки содержи­мого ящика меньшее число будет также предшествовать большему.