Valery Makarov

Bead Sort

Algorithms

Today we’re going to review an algorithm that was invented 11 years ago. Its “prototype” is a counting device with three thousand years of history.

Authors

Bead Sorting Algorithm Authors The sort was presented in 2002 by three mathematicians from the University of Auckland, New Zealand. They are Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen. They work in such fields as discrete mathematics, the theory of number, quantum computations, the information theory and combinatorial algorithms.

Abacus sortI’m not sure, which one of them was the first to come up with the idea. Perhaps, Calude, since he also professes the History of Computing Mathematics. Everybody knows that the progenitor of counting in Europe was abacus. It moved on from Babylon to Egypt, then to Greece, Rome and, finally, the whole Europe. The appearance and operating principle of the ancient “calculator” is reminding of the “simple” sort behavior so much that it’s sometimes called Abacus sort.

Algorithm

Bead Sort Algorithm Suppose, we need to sort out a set of natural numbers. We’ll place each number one under another in the form of a horizontal row from the appropriate number of beads. Now let’s take a look at these bead groups not horizontally, but vertically. Move the beads down to the stop. Now count the beads in each horizontal row. We’ve got a primary set of numbers and it’s ordered.

Implementation

You will find the Bead sort in more than 30 programming languages here. Despite the fact that the algorithm looks pretty simple, the implementation is not that trite.

Degenerated Case

Bead Sort Algorithm It’s a reversely ordered array. A maximum number of beads will have to fall down from the highest points.

Limited Applicability

This method can be applied mostly to natural numbers.

We can also sort integers, but it’s more complicated, since we’ll have to process negative numbers separately from positive ones.

Nothing prevents us from sorting fractional numbers. But we should cast them to integers before that (for instance, multiply everything by 10^k, sort it out, and then divide by 10^k)

Also, we can definitely sort strings, if we represent each of them as a positive number. But what for?

Time Complexity

There are four sorting complexities, depending on the context we consider the algorithm in.

O(1)

Bead Sort Algorithm It’s an abstract case, a spherical Bead sort in the vacuum. Imagine that all beads moved simultaneously and take their places. This complexity cannot be implemented in practice or the algorithm theory.

O(√n)

It’s the estimation for the physical model, in which beads slide down along the greased spokes. The time of free fall is proportional to the square root of the maximum height, which is proportional to n.

O(n)

The beads that haven’t reached their places are moved one row at a time. This complexity is appropriate for physical devices that implement such sorting and also analogous or digital hardware implementations.

O(S)

Bead Sort Algorithm S – is the sum of the array elements. Each bead is moved on individually. They are not moved in groups simultaneously. It’s an adequate evaluation of the complexity for implementation in programming languages.

Memory Complexity

It leaves much to be desired. Bead sort is the record-holder as for waste. The costs for the extra memory exceed the costs for storing the array itself. They’re O(n2) on overage.

Physics

Bead Sort Algorithm Physics The presence or absence of beads can be interpreted as the analogue voltage going through a series of electric resistors. Poles that are used to move the beads are analogues of electric resistors, in which voltage increases downwards.

If you’re an expert in electrostatics, please refer to this document(PDF).

In Practice

Bead sort – is a form of a sort by counting. The number of beads in each vertical row is the number of elements in an array. The elements are equal to or bigger than the order number of the vertical.

Characteristics of the Algorithm

Name: Bead sort; Abacus sort Authors: Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen Year of publication: 2002 Class: Distribution Sort Stability: Stable Comparisons: No comparisons Time Complexity: O(1), O(√n), O(n), O(S) Memory Complexity: O(n^2)

References

The authors’ homepages:

Comments

    Flux 3,751

    Ropes — Fast Strings

    Most of us work with strings one way or another. There’s no way to avoid them — when writing code, you’re doomed to concatinate strings every day, split them into parts and access certain characters by index. We are used to the fact that strings are fixed-length arrays of characters, which leads to certain limitations when working with them. For instance, we cannot quickly concatenate two strings. To do this, we will at first need to allocate the required amount of memory, and then copy there the data from the concatenated strings.