Пользователь
0,1
рейтинг
25 октября 2013 в 05:40

Разработка → Бисерная сортировка (Bead sort)


Сегодня предложу Вашему вниманию симпатичный алгоритм, который хоть и придумали совсем недавно (11 лет назад), но «прототипом» послужило счётное устройство с трёхтысячелетней историей.


Авторы



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

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

Алгоритм


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

Реализация


Bead sort на 30+ языках программирования можно найти здесь. Хотя визуально алгоритм выглядит проще некуда, с точки зрения программной реализации это весьма нетривиальная сортировка.

Вырожденный случай


Таковым является реверсно упорядоченный массив. Максимально возможному количеству шариков придётся рухнуть с наивысших точек.

Ограниченная применимость


Метод прежде всего применим к натуральным числам.

Можно сортировать и целые, но это запутаннее – отрицательные числа придётся обрабатывать отдельно от положительных.

Ничего не мешает сортировать и дробные числа, если перед тем привести их к целым (например, всё умножить на 10k, отсортировать, а потом разделить на 10k).

Ну и, конечно, так можно сортировать даже строки, если каждую из них представить в виде целого положительного числа. Но зачем?

Сложность по времени


Их у сортировки аж 4, смотря в каком контексте рассматривать алгоритм.


O(1)


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

O(√n)


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

O(n)


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


O(S)


S – сумма элементов массива. Каждый шарик перемещается по отдельности, а не перекатываем группы шариков одновременно. Адекватная оценка сложности для реализации на языках программирования.

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


Оставляет желать лучшего. Bead sort рекордсмен расточительности – расходы на дополнительную память многократно превышают затраты на хранение самого массива и в среднем составляют O(n2).

Физика



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

Не пинайте за косноязычное использование электротехнических терминов, у меня в школе по физике была тройка с плюсом четвёрка с минусом.

Знатоков электростатики отсылаю за подробностями в этот pdf-документ.

На самом деле


Bead sort – это разновидность сортировки подсчётом. Количество шариков в каждой вертикальной дорожке – это количество элементов в массиве, равных или больших чем порядковый номер вертикали.

Характеристики алгоритма


Название Бисерная сортировка (Bead sort); Абаковая сортировка (Abacus sort)
Авторы Джошуа Дж. Аруланандам, Кристиан С. Калуд, Майкл Дж. Динин
Год публикации 2002
Класс Сортировка распределением
Устойчивость Устойчивая
Сравнения Без сравнений
Временная сложность O(1) O(√n) O(n) O(S)
Сложность по памяти O(n2)

Ссылки

Бисерная сортировка на сайте Оклендского университета
Авторская документация по алгоритму, pdf
Реализация на различных ЯП
Bead sort в анлийской Википедии

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

Джошуа Дж. Аруланандхам
Кристиан С. Калуд
Майкл Дж. Динин
Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (41)

  • +10
    > Ничего не мешает сортировать и дробные числа, если перед тем привести их к целым (например, всё умножить на 10k, отсортировать, а потом разделить на 10k).

    Ничего, кроме необходимости выделить 10k памяти.
    • 0
      Вовсе нет, если речь о Double, то ничего не изменится. Проблемой тут будет только вылет возможных сортируемых значений за предел double при умножении.
    • +13
      Хабр, ты окончательно ебанулся.
      Под эту сортировку выделяется N * Max памяти, где N — число элементов, max — максимальная величина элемента. В любую реализацию гляньте, блин.
      for (i = 1, max = a[0]; i < len; i++)
      		if (a[i] > max) max = a[i];
       
      	beads = calloc(1, max * len);
       

      На сортировку N целых чисел, таким образом, нужно N * Max * sizeof(int) памяти.
      На сортировку дробных чисел нужно будет N * round(Max * 10k) * sizeof(int) памяти, потому что умножение на 10k увеличивает максимальное значение. Это верно вообще для всех сортировок вычёрпыванием.
      Технический ресурс, my ass.
      • +3
        Не надо так переживать. Неэффективные алгоритмы тоже полезны для рассмотрения, как в методологических, так и педагогических целях.
        • +7
          Причем здесь неэффективные алгоритмы? Я переживаю за пять минусов у технически корректного комментария.
          • +2
            Рискну предположить что минусы не за техническую корректность :)
            • +2
              Прям затрудняюсь понять, чьи нежные чувства я задел фразой «Ничего, кроме необходимости выделить 10k памяти.»
              • 0
                Ах, да, я имел в виду вашу реплику чуть ниже. Точно, там ведь (на текущий момент) 6 минусов, а не 5 :)

                Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.

                • +2
                  > Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.

                  • –1
                    Ах да, точно! )

                    Мы же их на единицы раскладываем. Тогда понадобится. )
                  • 0
                    Это всё от того, что на анимации в посте показан вырожденный случай — ряд сортируемых элементов содержит все элементы, от первого до последнего, без пустых мест. Если бы показывали сортировку ряда «0-2-4-6-8-10», то стало бы очевидно — для такой сортировки потребуется таблица 6 столбцов * 11 строк.
                    Ну и некоторые, типа меня, не проснулись к моменту чтения поста.
                    >>Ничего, кроме необходимости выделить 10k памяти.
                    Вы хотели сказать «10k памяти на каждую строку» — разница довольно существенна.
  • +2
    Аааа, жуткая сортировка. А если надо сортировать 64битные числа, где же столько памяти взять?
    • +7
      Это статья о страшной сортировке в честь надвигающегося Хеллоуина :)
  • +4
    С выделяемой памятью конечно перегиб — недопустимые в реальных проектах объемы. Но сортировка интересна и проста. Спасибо топикстартеру за интересный и хорошо оформленный пост.
  • 0
    Какое-то странное описание алгоритма. Если выкинуть из него физические шарики — то получится всем известная сортировка подсчетом, с временем работы O(n+m) и такой же требуемой памятью. Здесь n — количество сортируемых чисел, а m — количество возможных значений сортируемых чисел.
    • 0
      O(n2) — это худший случай по памяти. Максимальное количество возможных значений n сортируемых натуральных чисел как раз равно n. В худшем случае m = n.

      Почему при оценке памяти именно умножение, а не сложение? Потому что изначально входной массив из n элементов, а дополнительно приходится обрабатывать матрицу n x n (в худшем случае).

      Насчёт counting sort. Да, бисерная сортировка — это сортировка подсчётом, но только через «одно место», ухудшенный вариант. Вместо того чтобы обрабатывать сами сортируемые числа, мы обрабатываем каждую единичку каждого числа. Всего единиц в массиве натуральных чисел равно сумме всех чисел S, отсюда и временная сложность O(S).

      Сортировать бусинками невыгодно с какой стороны ни посмотри, но для пятничного поста алгоритм вполне годится :)

      • 0
        В худшем случае m = n.
        Вы ошибаетесь. В худшем случае m много больше n. Так, при сортировке миллиона «обычных» чисел n=10^6, m=2^32. Именно такой эффект и ограничивает применимость сортировки подсчетом.
        • 0
          Может быть. Мне тоже изначально не нравится O(n2), просто решил не перечить оклендским математикам, а предоставить опровержение хабраюзерам прочитавшим эту статью.
  • 0
    Если я правильно понял, то самое интересное в том, что сложность может быть меньше, чем O(n log(n)); а это минимум для сортировки сравнением.
    • +2
      O(n log n) — это минимум для сортировок абстрактных элементов с определенной на них функцией сравнения. Т.е. алгоритм ничего не знает ни о природе элементов, ни об их начальном расположении.

      Здесь же сортируются исключительно натуральные числа и алгоритм использует их свойства. Еще пример — поразрядная сортировку с временем O(nk).
    • 0
      Да, самое интересное в семействе сортировок подсчетом — тот факт, что сложность может быть меньше Ω(n log n)
  • +10
    Я бы сменил хаб «Совершенный код» на «Ненормальное программирование» :)
    • +1
      Пожалуй, да )
  • +2
    А кст, хоть и узко-специализированная, зато в редких случаях может быть крайне полезной. В копилку.

    З.Ы. ссылочка на реализацию утянула на 30 минут рассматривания синтаксисов :)
  • +6
    При чём тут Абак? Ладно, представим, что у нас есть «физический процессор» с падающими шарами и оттуда получается такая сложность O(n**0.5), но что за сложность O(1)? И можно ли любому алгоритму придать такую сложность с приписом «всё одновременно сдвигается и считается»?
    • 0
      Чаще всего сортировку наглядно представляют как бисер нанизанный на спицы. Или как шарики, скатывающиеся по узким желобкам. Второй вариант мне был проще для создания анимации.

      O(1) — это результат некоего теоретизированного рассуждения, мысленный эксперимент с участием идеального физического устройства в идеальных условиях, реализующего эту сортировку. Если абсолютно исключить трение, поместить устройство вблизи сверхмассивного тела, мгновенно и одномоментно предоставить шарикам возможность упасть вниз по спицам — то временная сложность будет стремиться как раз к такому значению. Как-то так.
      • +2
        Вы забыли, что шарики следует сначала разместить (по-одному), а потом еще и подсчитать обратно.

        Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти. Простите за корявую формулировку, но более точные формулировки хуже передают суть.
        • 0
          >>> Вы забыли, что шарики следует сначала разместить (по-одному), а потом еще и подсчитать обратно.

          Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия. Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.

          >>> Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти.

          Бисерная сортировка примечательна тем, что её часто рассматривают не как алгоритм/программу, а как некое физическое устройство с шариками на спицах или электрическую цепь из резисторов. Речь о памяти в этом случае просто не идёт.
          • +4
            Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.
            Нет, но при этом я подсчитываю время, которое потребуется на считывание исходных данных из входного файла.
  • –1
    а реализация на квантовом компьютере не будет иметь О(1)? чисто теоретически?
    • 0
      Ой, промахнулся, смотрите моим комментарием ниже.
  • 0
    Надо будет на досуге отписаться авторам сортировки и спросить у них. В конце концов, они все специалисты по квантовым вычислениям.
  • +6
    Алгоритм абсолютно безумный, но на реализации на RosettaCode поглядеть забавно. Как элегантно выглядит реализация на Хаскеле:

    import Data.List
     
    beadSort :: [Int] -> [Int]
    beadSort = map sum. transpose. transpose. map (flip replicate 1)
    
  • 0
    Не понятно, как в такой сортировке данные к ключу привязывать? Т.е. например отсортировать строки в таблице по натуральному ключу?
    А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
    • +1
      >>> Не понятно, как в такой сортировке данные к ключу привязывать?

      В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.

      >>> Т.е. например отсортировать строки в таблице по натуральному ключу?

      Алгоритм использует свойства натуральных чисел и поэтому «заточен» прежде всего под упорядочивание целых чисел больше нуля.
      Сортировать бисером можно и что-то другое, строки в том числе (можно придумать какие-то способы приведения строку в целое число и обратно), но это уже извращение. Сортировка изначально придумана под натуральные числа.

      >>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?

      Сортировка подсчётом во всех отношениях намного эффективнее чем бисерная сортировка. Более того — бисерная сортировка это разновидность сортировки подсчётом, причём разновидность весьма медленная и крайне расточительно использующая память.

      Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.
      • 0
        Вот, кстати, подумал, что не знаю, как назвать класс сортировок, которые основаны на обмене элементов. Т.е. в отличии от бисерной или подсчетом сохраняют возможность связи с данными.

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

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

        • 0
          Сортировки бывают таких видов:

          Сортировки обменами
          Сортировки вставками
          Сортировки выбором
          Сортировки слиянием
          Сортировки распределением
          Гибридные сортировки
          Параллельные сортировки

          Быстрая относится к обменным.

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

          Они обычно работают быстрее чем известные эффективные сортировки других видов (quick sort, merge sort, heap sort и кое-какие другие) но Вы точно заметили их существенный недостаток: ограниченная применимость (обычно заточены под целые числа или строки).

          Быстрая сортировка работает очень быстро и она универсальна. Поэтому она так популярна и широко используема. Но для каких-то узких специфических задач другие сортировки могут работать намного быстрее.
        • 0
          Сортировка подсчетом сохраняет возможность связи с данными. Более того, она при этом еще и является устойчивой.

          Кстати, на данном свойстве сортировки подсчетом основывается поразрядная сортировка.
      • 0
        Ах да. Еще небольшое замечание.
        На вопрос:
        >> Не понятно, как в такой сортировке данные к ключу привязывать?
        Вот такой ответ:
        >В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
        подразумевает, что в этих реализациях раскрывается способ, как привязать.
        Однако это не так. Видимо, правильный ответ: ни как. Как и в сортировке подсчетом.
        • 0
          В общем, никак. Распределительные сортировки в силу их специфических методов, ключи не запоминают.
        • 0
          Как и в сортировке подсчетом.
          Что же вы так…

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.