9769

Extended Bead-Sort

Bead-Sort is a method of ordering a set of positive integers by mimicking the natural process of objects falling to the ground, as beads on an abacus slide down vertical rods. The number of beads on each horizontal row represents one of the numbers of the set to be sorted, and it is clear that the final state will represent the sorted set. In this Demonstration the sorting process can be run or stepped through, two sample sizes selected, and new random datasets generated. The "extended" (anti-gravity) mode allows the inclusion of all integers, with "negative beads" rising while "positive beads" fall.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The Bead-Sort algorithm [1] has drawn interest because of its promise of faster sorting times for positive integers, and as an excellent example of extracting an algorithm from a simple natural process (in this case, falling under the influence of gravity).
Snapshot 1: after gravity has pulled all the beads to the bottom, the rows represent the sorted set of non-negative integers; note that 0 is allowed and will automatically "rise to the top" as the beads settle to the bottom
Snapshot 2: an odd feature of the algorithm is that interim results may actually include numbers (here shown in red) that were not in the original set, but the sorted end result is still guaranteed
Snapshot 3: a larger set of non-negative integers to sort: the Initial/Interim/Sorted lines are suppressed
Speed and Complexity
There has been some confusion about the actual speed of the Bead-Sort algorithm. In their initial paper [1], Arulanandham, Calude, and Dinneen (ACD) suggested that depending on the user's perspective the sort might theoretically be considered , , or —that is, independent of the set size, varying linearly with it, or varying with the sum of the integers in the set. Since comparison sort methods are or (which is the best average case, as in quicksort, for instance [2]), this is an exciting prospect, although it turns out to be unrealizable in software implementations. We consider the cases in turn:
: This can only be justified by treating the falling of all the beads together as a single event independent of the number of beads, but it is difficult to see how it could be achieved in practice, even in a physical model, since the time necessary for an object to fall in a uniform gravitational field is proportional to the square root of the distance, and the beads would need to fall a maximum distance proportional to , making the physical model for the sorting stage [3], but for loading the inputs.
: This can be realized in a hardware implementation that handles the columns in parallel. The ACD paper discusses two such hardware implementations (explained below), with the "beads" introduced one row at a time, each "bead" falling immediately to the lowest possible position in its column: behavior mimicked by the "hardware" mode in this Demonstration (although not actually realizable by software). If the beads are already in place, the parallel processing (as done by a hardware implementation) can still make the sort if at each step all beads above gaps fall simultaneously and immediately as far as the next lower bead. This is modeled visually by the "gap" setting.
Even if beads are only allowed to fall one position per time step (as in shown in "single" mode), time may be saved if the setup and settling phases are not separated, if new rows are introduced one at a time at the top while the previously placed beads are still settling. The total time is no more than , the sum of the number of rows and columns of the array, needing time steps for the loading (while settling proceeds) followed by at most time units for the remainder of the settling process after the last row enters the system—assuming comparable times for loading a new row and one settling step.
: This is the best time that Bead-Sort can achieve without parallel treatment of columns: either introducing rows from the top, or with rows in place and beads scanned starting with the bottom row and continuing upward, we allow each bead to fall as far as it can. The time is proportional to , the total number of beads, which is no more than . (Straightforward software implementations are far more time intensive, however.)
Hardware Implementations of Bead-Sort
ACD proposed analog and digital hardware implementations using a graduated array of resistors or an array of triggered flip-flops, respectively, where rows of "beads" enter the top of the system and settle immediately to the lowest available level—not cascading down the columns one level at a time. This parallelization (treating all columns simultaneously) and short-circuiting the cascading process guarantees the sorting time. The analog implementation successively adds "beads" to resistor columns as voltage increments, which causes changes in the voltage levels across each resistor below, which then indicates the presence/absence of a bead at each position of the frame, given appropriate choices of voltage increment and threshold voltage, and the resistances to be used at each level. In the digital implementation, at each time step "beads" (0s or 1s) are loaded into a buffer register Bead[i] and then "dropped" into the main array of flip-flops, going directly to its final position in the array. This is achieved by a clever yet simple triggering condition for the individual cells: Cell[i,j] starts in the 0 state and will change to the 1 state if and only if . (See [1] for details on both implementations.)
Software Implementations
The direct software implementation of Bead-Sort is a two-dimensional cellular automaton (CA). ACD consider state changes of the entire CA as simultaneous, effectively requiring massive parallelization in order to again claim a sort time of . However, in a nonparallelized algorithm, the whole array must be scanned and updated for each CA update, giving a slow . This is what is actually happening behind the scenes in this Demonstration, although the image is only updated after each iteration of the whole array. In ill-behaved scenarios, beads may be temporarily blocked from falling by the presence of one or more beads beneath it that must fall first. (Run the Demonstration a few times, such cases occur rather frequently.)
Implementations that do not update the entire array at each step can have order . Treating only beads (i.e., filled cells, not empty cells) can reduce this to , where is the sum of all the numbers to be sorted. But of course this is still slower than alternative sort schemes.
Besides the significantly slower software implementation, other drawbacks of the Bead-Sort algorithm that have been pointed out [4] include a large memory requirement, —or if an actual matrix transpose is performed, the larger of and —and the algorithm's (assumed) limitation to sets of positive integers. These difficulties have limited the practical value of Bead-Sort as a software algorithm.
Antigravity Bead-Sort
The limitation to positive integers is lifted by the present extension to the algorithm, which we have called Antigravity Bead-Sort for reasons obvious from the Demonstration itself: we allow the inclusion of negative integers (or zero), and add the rule that "negative beads" rise while "positive beads" fall. (Allowing 0 as an element of the set was implicit in the original Bead-Sort algorithm, although not explicitly stated before the present work: in fact, the rising of zeros can be viewed as motivation for the treatment of negative numbers.)
Snapshot 4: the "Antigravity Bead-Sort" (Extended Mode) handles negative integers by allowing "negative beads" (shown in green) to rise while "positive beads" fall
Despite the rather provocative name for our extension of the algorithm, there is ample motivation from nature for the Antigravity Bead-Sort. For example, consider the behavior of a set of positive and negative charges in a uniform downward-directed electric field: the positive charges all accelerate downwards (a direct correlation to the behavior of masses in a constant gravitational field), while the negative charges accelerate upwards. Perhaps an even closer physical analogy would be the release of two types of balls underwater: all the same size, but "positive" and "negative" balls having a density greater than or less than that of water, respectively. In such a case the movement would quickly reach some (slow) terminal velocity, dependent on the density and radius of the balls, and would exhibit behavior analogous to the relatively steady motions observed here in "clump" mode with all beads/balls moving together. This uniform motion case could also model the penetration of successive membranes, a case also considered by Arulanandham [5] in a scenario that could be extended in a straightforward manner to allow opposite direction penetration by "positive" and "negative" objects.
Implementation of the Extended/Antigravity Bead-Sort
A direct extension of the analog and digital hardware implementations proposed by ACD requires no new particles and no antigravity: we simply create a duplicate setup (of resistors or flip-flops, respectively) for the "negative bead columns". Negative numbers are introduced into the system in the new columns; positive numbers are treated as before. The direction of motion in the new columns is taken to be opposite (rising instead of settling), but no hardware changes need actually be made.
Cellular Automata Implementation
The Bead-Sort can be modeled by the two-dimensional cellular automaton (CA) rule, .
For the Antigravity Bead-Sort, we add a second rule: .
The Mathematica rules (applied to the transposed matrix) are
{{x___, 1, 0, y___} :> {x, {0, 1}, y}, {x___, 0, -1, y___} :> {x, {-1, 0}, y}}.
(The rules are applied using ReplaceRepeated (//.) so as to move multiple beads in each column, the extra-curly brackets temporarily inserted prevent any one bead or group of beads from moving twice in a given step.)
An "instantaneous" drop for one bead above a gap (and the comparable motion of a negative bead rising through a gap) can be modeled by the rule set
{{x___, 1, z: Longest[0 ..], y___} :> {x, {z, 1}, y}, {x___, z: Longest[0 ..], -1, y___} :> {x, {-1, z}, y}}.
It is also easy to allow whole collections of beads to fall/rise simultaneously either one step at a time or through gaps. The "clump" setting uses the rule set
{{x___, u : Longest[1 ..], 0, y___} :> {x, {0, u}, y}, {x___, 0, u : Longest[-1 ..], y___} :> {x, {u, 0}, y}}.
These rules operate by looking for longest matching sequences, and result in fewer steps but more comparisons needed per step, again making the hardware speeds unattainable for a non-parallelized software algorithm.
"Arrayless" Bead-Sort Software Implementation
As has been pointed out above, the CA implementation is not only quite slow, but requires an matrix, thus having a space requirement of at least . But it is possible to dispense with the array altogether, characterizing the columns by a list of counters. Adding beads to the columns is accomplished by simply incrementing the appropriate columns' counters, and the sorted list can then be reconstructed from the counters without creating a matrix to transpose. One way to implement this in Mathematica is as follows:
ArraylessBeadSort[l_List] := Module[{counter, n, i},
counter[n_] := 0;
(++counter[#] & /@ Range[#]) & /@ l;
i = 0; n = Length[l];
Reap[
While[counter[i] ≠ 0 || i ⩵ 0 ;
If[# < n, Do[Sow[i], {n - #}]; n = #] & @ counter[i + 1];
i++]
]〚-1, -1〛]
This algorithm has a space requirement of only , and runs at , a significant improvement over the CA implementation. As written, it will sort arbitrary length sets of non-negative integers. Allowing negative integers can be done by adding counters for the negative integer columns, as described above.
References:
[1] J. J. Arulanandham, C. S. Calude, and M. J. Dinneen, "Bead-Sort: A Natural Sorting Algorithm," The Bulletin of the European Association for Theoretical Computer Science, 76, 2002 pp. 153–162.
[2] D. Knuth, The Art of Computer Programming (Volume 3: Sorting and Searching), 3rd ed., Reading, MA: Addison–Wesley, 1997.
[3] "Bead Sort".
[4] D. Schultes, "On the Practical Use of Bead Sort," 2004.
[5] J. J. Arulanandham, "Implementing Bead-Sort with P Systems," CDMTCS Research Report, 186, 2002.

RELATED LINKS

    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+