Вёдерная сортировка :: Bucket sort
Мета-алгоритм. являющийся основой целых семейств сортировок, в частности, сортировок подсчётом и поразрядных сортировок.
Алгоритм
Основная идея - распределяем элементы по вёдрам (блокам, карманам, корзинам), т.е. группируем их по определённому признаку. Элементы в каждом ведре группируем по уточняющим признакам. Продолжаем процесс распределения, пока в каждом ведре не окажутся одинаковые элементы.
Характеристики алгоритма
| Название | Вёдерная сортировка (Bucket sort) | |
|---|---|---|
| Другие названия | Карманная сортировка,корзинная сортировка,блочная сортировка | |
| Класс | Сортировки распределением | |
| Устойчивость | Да / Нет | |
| Сравнения | Нет / Да | |
| Сложность по времени | Худшая | O(n2) |
| Средняя | O(n + k) | |
| Лучшая | O(n) | |
| Сложность по памяти | Худшая | O(n × k) |
Вёдерная сортировка