Bead Sort in MGS



Principles

Bead sort is a new sorting algorithm designed by J. J. Arulanandham, C. S. Calude and M. J. Dinneen (EATCS Bull. 76 (2002)). The idea is to represent positive integers by a set of beads, like those used in an abacus. Beads are attached to vertical rods and appear to be suspended in the air just before sliding down (a number is read horizontally, as a row). After their falls, the rows of numbers have been rearranged such as the smaller numbers appears on top of greater numbers. The corresponding MGS program is just one line long. In the following picture, a bead is rendered by a small black ":" sign.

bead sort of a set of number. The gravity rearrange the bead such as the greater number fall down.



The corresponding MGS program




specifying an abacus and the bead-sort algorithm

gbf abacus = < rods, levels >;;

Definition of a GBF type. GBF means Group Based Fields. A GBF specifies a uniform topology where the element are indexed by a mathematical group. Here, all elements in an instance of the GBF  type abacus has two neighbors: one following the direction rods, the other following the direction levels. (and also two others neighbors reached following the inverse directions).

This is juste the way in MGS to define a 2D array whose dimensions are named rods and levels.

trans do_sort = {
    "|" |rods> " "  =>  " ", "|"
};;

We suppose that the numbers are represented in unary base by a series of "|" along the levels dimension. An "empty space" in the abacus is represented by the string " " (this string contains only one character, the white-space).

The core of bead-sorting is simply implemented as one rule that defines the exchange of a bead "|" on top of an empty space.
fun sort(liste) = do_sort[*](prepare(liste)) ;;
To sort a list of number, it is sufficient to represent this list of number in the abacus representation and then to iterate the basic exchange of a bead and an empty space. The optionnal argument [*] in the application of transformation do_sort specifies that the transformation must be iterated until a fixpoint is reached.
The coding of a list of numbers into an abacus is done by the function prepare which takes a list of number as an argument.



transforming a list of numbers into an abacus

fun int_to_nat(x) =
   if (x == 0) then seq:() else "|",int_to_nat(x-1) fi;;

Take an int x and return a sequence of "|". The length of this sequence is x. This function uses a simple recursion on x.
Example : int_to_nat(3) returns "|", "|", "|"
fun produce_zeros(n) =
   if (n == 0) then seq:() else " ",produce_zeros(n-1) fi;;

Produce a sequence of n elements " ".
Example : produce_zeros(4) returns " ", " ", " ", " "
fun pad(len, v) =
    v,produce_zeros(len-size(v));;

Takes an integer len and a sequence v and completes the sequence v by leading " " to build a final sequence of length len.
Example: pad(5, ("|","|","|"))
returns "|", "|", "|", " ", " "
fun max_of_list(l) =
    if (l == seq:())
    then 0
    else max(hd(l), max_of_list(tl(l)))
    fi;;

Computes the maximum of a list of integers by recursion (hd and tl gives the head and the tail of a sequence, seq:() denotes the empty sequence).

Note that others methods are possible, e.g. using a fold operator :
fold(max, 0, s) returns the maximum of the positive elements in the sequence s.
fun prepare(liste) =
    let long = max_of_list(liste)
    in map((\x. pad(long)(int_to_nat(x))), liste)
       following  |rods>, |levels>;;

Takes a list of integers and returns an abacus.
The variable long represents the maximal number in the list, and hence, the width of the abacus. Each element in the list is transformed into a sequence of "|" padded to this width. So the first argument of following (an infix operator) is a list of lists. The second argument of following is a sequence of directions in a GBF. Each level of the nested lists is mapped into the corresponding direction into the second argument. For example,
(a, a, a) :: (b, b) :: (c, c, c, c) :: seq:()
following
|rods>, |levels>

returns the the abacus
a, a, a
b, b
c, c, c, c
(we assume that the rods dimension is mapped horizontally and levels is mapped vertically).



Back to top
MGS examples index
MGS home page



(currently under construction logo)
this site is under construction.
Pages started: May 2002. Last revision: 24 jully 2003.

Creative Commons License
Pictures, graphics and animations are licensed under a Creative Commons License.


English keywords for indexation: computer science, programming language, topological collections, transformation, declarative programming language, functional languages, simulation of biological processes, cell model, biological pathway, interaction network, gene regulation, signal transduction, morphogenesis, developmental biology, integrative simulation, biological organization, dynamical systems, dynamical structure, Gamma, CHAM, P system, L system, Paun, Lindenmayer, cellular automata, membrane computing, aqueous computing, artificial chemistry, GBF, Cayley graph, data fields, nested collections, rewriting, rule based programming, pattern-matching, intentional programming, compilation, interpretation, type, type inference, nested type, polytypism, catamorphism, static analysis, sequence, multiset, combinatorial algebraic topology, chain complex, chain group.