Extended Bead-Sort

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

Contributed by: Kenneth E. Caviness and Erik S. Caviness (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send