Бисерная сортировка :: 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 в английской Википедии

Домашние странички авторов:

Джошуа Дж. Аруланандхам
Кристиан С. Калуд
Майкл Дж. Динин

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