Вёдерная сортировка :: 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