## 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. ## 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). this site is under construction.
Pages started: May 2002. Last revision: 24 jully 2003.   