Вёдерная сортировка :: Bucket sort

Мета-алгоритм. являющийся основой целых семейств сортировок, в частности, сортировок подсчётом и поразрядных сортировок.

Алгоритм

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

Вёдерная сортировка

Например, в данной анимации, все числа распределяются по сотням (поскольку в данном массиве числа от 100 до 299, то в одно ведро кидаются элементы менее 200, в другое — более 200). Затем каждое ведро раскидывается в вёдра поменьше по десяткам (100-110, 111-120, 121-130 и т.д.) Ну, и затем, распределяется по единицам.

Легко заметить, что данная реализация вёдерной сортировки — не что иное как поразрядная MSD-сортировка.

Если не распределять по степеням десятки, а, к примеру, выбирать элемент в массиве и затем в одно ведро кидать то что меньше выбранного элемента, а в другое — то что больше, и затем рекурсивно применить к каждому ведру — то это не что иное как быстрая сортировка.

Характеристики алгоритма

Название Вёдерная сортировка (Bucket sort)
Другие названия Карманная сортировка,
корзинная сортировка,
блочная сортировка
Класс Сортировки распределением
Устойчивость Да / Нет
Сравнения Нет / Да
Сложность по времени Худшая O(n2)
Средняя O(n + k)
Лучшая O(n)
Сложность по памяти Худшая O(n × k)

Ссылки

Вёдерная сортировка в Википедии
Bucket sort on Wikipedia

Добавить комментарий