Бисерная сортировка :: Bead sort

Бисерная сортировка

Сортировку презентовали в 2002 году три математика из Университета Окленда, что в Новой Зеландии: Джошуа Дж. Аруланандам (Joshua J. Arulanandham), Кристиан С. Калуд (Cristian S. Calude) и Майкл Дж. Динин (Michael J. Dinneen). Сферы деятельности учёных – дискретная математика, теория чисел, квантовые вычисления, теория информации, комбинаторые алгоритмы.

Бисерная сортировка, авторы: Джошуа Дж. Аруланандам (Joshua J. Arulanandham), Кристиан С. Калуд (Cristian S. Calude), Майкл Дж. Динин (Michael J. Dinneen)

Бисерная сортировка
Не знаю, кому из них троих принадлежит первоначальная идея. Возможно Калуду, который помимо всего прочего преподаёт историю вычислительной математики. Все знают, прародителем счётов в Европе является абак, который из Вавилона перекочевал в Египет, оттуда – в Грецию, из неё – в Рим, из которого – по всей Европе. Внешний вид и принцип действия античного «калькулятора» настолько напоминает поведение этой «простой» сортировки, что её иногда так и называют — «Абаковая сортировка» (Abacus sort).

Алгоритм

Имеется неупорядоченный набор натуральных чисел.

Друг под другом выложим каждое число в виде горизонтальных рядов из соответствующего числа шариков. Сдвинем шарики в вертикальном направлении "вниз" до упора.

Пересчитаем снова количества шариков в горизонтальных рядах. Получили первоначальный набор чисел, только упорядоченный.

Сложность по памяти

Зависит от конкретной реализации сортировки.

O(1)

Бисерная сортировка за O(1)
Абстрактный случай, сферическая Bead sort в вакууме. Если представить, что все перемещаемые шарики одновременно сдвигаются и встают на свои места. Это нереализуемая сложность для этой сортировки – ни в теории алгоритмов, ни на практике.

O(√n)

Оценка для физической модели, где бусинки скользят вниз по хорошо смазанным спицам. Время свободного падения пропорционально квадратному корню максимальной высоты, которая в свою очередь кратна n.

O(n)

Шарики, которые ещё не добрались до своих мест, дружно перемещаются на одну позицию вниз за одну итерацию. Об этой сложности уместно говорить в случае физических устройств, реализующих такой способ сортировки, аналоговых или цифровых аппаратных реализаций. Также это сложность для параллельной реализации данной сортировки.

O(S)

Бисерная сортировка за 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

Джошуа Дж. Аруланандхам

Кристиан С. Калуд

Майкл Дж. Динин