Сортировка бусинами (Bead Sort): алгоритм сортировки, разработанный в 2002 году. Оптимальна для аппаратной реализации, медленна в ПО, подходит для положительных чисел.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Сортировка бусинками, также называемая сортировкой гравитацией, — это естественный алгоритм сортировки, разработанный Джошуа Дж. Аруланандамом, Кристианом С. Калуде и Майклом Дж. Диннееном в 2002 году и опубликованный в журнале The Bulletin of the European Association for Theoretical Computer Science. Как цифровые, так и аналоговые аппаратные реализации сортировки бусинками могут достигать времени сортировки O(n). Однако программная реализация этого алгоритма, как правило, значительно медленнее и может использоваться только для сортировки списков положительных целых чисел. Кроме того, даже в лучшем случае алгоритму требуется O(n²) памяти.
Bead sort, also called gravity sort, is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in The Bulletin of the European Association for Theoretical Computer Science. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n2) space.
Обзор алгоритма
Сортировку бусин можно сравнить с тем, как бусины скользят по параллельным столбам, например, на абаке. Однако на каждом столбе может быть разное количество бусин. Сначала может быть полезно представить бусины подвешенными на вертикальных столбах. На шаге 1 такая организация демонстрируется с использованием n=5 рядов бусин на m=4 вертикальных столбах. Числа справа от каждого ряда указывают число, которое представляет данный ряд; ряды 1 и 2 представляют положительное целое число 3 (поскольку каждый из них содержит три бусины), а верхний ряд представляет положительное целое число 2 (поскольку он содержит только две бусины). Если мы позволим бусинам упасть, ряды теперь будут представлять те же числа в отсортированном порядке. Ряд 1 содержит наибольшее число в наборе, а ряд n – наименьшее. Если была соблюдена вышеупомянутая условность, согласно которой ряды содержат бусины на столбах 1–k, а столбы k+1–m остаются пустыми, то это останется верным и здесь. Позволяя бусинам "падать" в нашем физическом примере, мы позволяем большим значениям из верхних рядов распространяться в нижние ряды. Если значение, представленное рядом a, меньше значения в ряду a+1, некоторые бусины из ряда a+1 упадут в ряд a; это обязательно произойдет, поскольку в ряду a нет бусин в этих позициях, чтобы остановить падение бусин из ряда a+1. Механизм, лежащий в основе сортировки бусин, аналогичен механизму сортировки подсчетом; количество бусин на каждом столбе соответствует количеству элементов со значением, равным или большим, чем индекс этого столба.
The bead sort operation can be compared to the manner in which beads slide on parallel poles, such as on an abacus. However, each pole may have a distinct number of beads. Initially, it may be helpful to imagine the beads suspended on vertical poles. In Step 1, such an arrangement is displayed using n=5 rows of beads on m=4 vertical poles. The numbers to the right of each row indicate the number that the row in question represents; rows 1 and 2 are representing the positive integer 3 (because they each contain three beads) while the top row represents the positive integer 2 (as it only contains two beads). If we then allow the beads to fall, the rows now represent the same integers in sorted order. Row 1 contains the largest number in the set, while row n contains the smallest. If the above mentioned convention of rows containing a series of beads on poles 1 k and leaving poles k+1 m empty has been followed, it will continue to be the case here. The action of allowing the beads to "fall" in our physical example has allowed the larger values from the higher rows to propagate to the lower rows. If the value represented by row a is smaller than the value contained in row a+1, some of the beads from row a+1 will fall into row a; this is certain to happen, as row a does not contain beads in those positions to stop the beads from row a+1 from falling. The mechanism underlying bead sort is similar to that behind counting sort; the number of beads on each pole corresponds to the number of elements with value equal or greater than the index of that pole.