Бисерная сортировка :: Bead sort
Сортировку презентовали в 2002 году три математика из Университета Окленда, что в Новой Зеландии: Джошуа Дж. Аруланандам (Joshua J. Arulanandham), Кристиан С. Калуд (Cristian S. Calude) и Майкл Дж. Динин (Michael J. Dinneen). Сферы деятельности учёных – дискретная математика, теория чисел, квантовые вычисления, теория информации, комбинаторые алгоритмы.
Не знаю, кому из них троих принадлежит первоначальная идея. Возможно Калуду, который помимо всего прочего преподаёт историю вычислительной математики. Все знают, прародителем счётов в Европе является абак, который из Вавилона перекочевал в Египет, оттуда – в Грецию, из неё – в Рим, из которого – по всей Европе. Внешний вид и принцип действия античного «калькулятора» настолько напоминает поведение этой «простой» сортировки, что её иногда так и называют — «Абаковая сортировка» (Abacus sort).
Алгоритм
Имеется неупорядоченный набор натуральных чисел.
Друг под другом выложим каждое число в виде горизонтальных рядов из соответствующего числа шариков. Сдвинем шарики в вертикальном направлении "вниз" до упора.
Пересчитаем снова количества шариков в горизонтальных рядах. Получили первоначальный набор чисел, только упорядоченный.
Сложность по памяти
Зависит от конкретной реализации сортировки.
O(1)
Абстрактный случай, сферическая Bead sort в вакууме. Если представить, что все перемещаемые шарики одновременно сдвигаются и встают на свои места. Это нереализуемая сложность для этой сортировки – ни в теории алгоритмов, ни на практике.
O(√n)
Оценка для физической модели, где бусинки скользят вниз по хорошо смазанным спицам. Время свободного падения пропорционально квадратному корню максимальной высоты, которая в свою очередь кратна n.
O(n)
Шарики, которые ещё не добрались до своих мест, дружно перемещаются на одну позицию вниз за одну итерацию. Об этой сложности уместно говорить в случае физических устройств, реализующих такой способ сортировки, аналоговых или цифровых аппаратных реализаций. Также это сложность для параллельной реализации данной сортировки.
O(S)
S – сумма элементов массива. Каждый шарик перемещается по отдельности, а не перекатываем группы шариков одновременно. Адекватная оценка сложности для реализации на языках программирования.
Сложность по памяти
Оставляет желать лучшего. Bead sort рекордсмен расточительности – расходы на дополнительную память многократно превышают затраты на хранение самого массива и в среднем составляют O(n2).Физика
Наличие или отсутствие шариков можно интерпретировать как аналоговое напряжение проходящее через серию электрических резисторов. Стержни, по которым перемещаются шарики – аналоги электрических резисторов, напряжение в которых увеличивается сверху вниз.
Характеристики алгоритма
| Название | Бисерная сортировка (Bead sort) | |||
|---|---|---|---|---|
| Другие названия | Абаковая сортировка (Abacus sort) | |||
| Авторы | Джошуа Дж. Аруланандам (Joshua J. Arulanandham), Кристиан С. Калуд (Cristian S. Calude), Майкл Дж. Динин (Michael J. Dinneen) | |||
| Год | 2002 | |||
| Класс | Сортировки распределением | |||
| Подкласс | Сортировки подсчётом | |||
| Устойчивость | Устойчивая | |||
| Сравнения | Без сравнений | |||
| Сложность по времени | O(1) | O(√n) | O(n) | O(S) |
| Сложность по памяти | O(n2) | |||
Ссылки
Бисерная сортировка (Bead sort)
Бисерная сортировка на сайте Оклендского университета
Авторская документация по алгоритму, pdf
Реализация на различных ЯП
Bead sort