Bead sort


    Today I will bring to your attention a nice algorithm, which, although it was just recently invented (11 years ago), the counting device with a three-thousand-year history served as a “prototype”.


    The authors



    Sorting presented in 2002, three mathematicians from the University of Auckland, in New Zealand: Joshua J. Arulanandam. (Joshua J. Arulanandham), Christian S. Kaludiya (Cristian S. Calude) and Michael J. Dineen. (By Michael J. Dinneen). The fields of activity of scientists are discrete mathematics, number theory, quantum computing, information theory, combinatorial algorithms.

    I do not know which of the three of them belongs to the original idea. Perhaps Kalud, who, among other things, teaches the history of computational mathematics. Everyone knows, the ancestor of accounts in Europe is the abacuswho migrated from Babylon to Egypt, from there to Greece, from it to Rome, from which throughout Europe. The appearance and function of the ancient "calculator" is so reminiscent of the behavior of this 'simple' sorting that it is sometimes called - " Abakovaya sort » (Abacus sort).

    Algorithm


    Suppose you want to sort a set of natural numbers . Under each other, lay out each number in the form of a horizontal row of the corresponding number of balls. Now let’s look at all these groups of balls not horizontally, but vertically . Push the balls all the way down. Again, switch to the horizontal and count the beads in each row. Got an initial set of numbers, only ordered.

    Implementation


    Bead sort in 30+ programming languages ​​can be found here . Although visually the algorithm looks nowhere simpler, from the point of view of software implementation, this is a very nontrivial sort.

    Degenerate case


    This is a reverse-ordered array . The maximum possible number of balls will have to collapse from the highest points.

    Limited applicability


    The method is primarily applicable to natural numbers .

    You can sort integers, but it's more complicated - negative numbers have to be processed separately from positive ones.

    Nothing prevents sorting and fractional numbers, if you first bring them to integers (for example, multiply everything by 10 k , sort, and then divide by 10 k ).

    Well, of course, even rows can be sorted in this way, if each of them is represented as a positive integer. But why?

    Time complexity


    There are already 4 of them in sorting, depending on the context in which to consider the algorithm.


    O (1)


    Abstract case, spherical bead sort in a vacuum. If we imagine that all the moving balls are simultaneously shifted and fall into place. This is an unrealizable complexity for this sorting - neither in the theory of algorithms, nor in practice.

    O (√n)


    An estimate for a physical model where beads glide down well-oiled knitting needles. The free fall time is proportional to the square root of the maximum height, which in turn is a multiple of n .

    O (n)


    Balls that have not yet reached their places, together move one position down in one iteration. It is appropriate to talk about this complexity in the case of physical devices that implement this sorting method, analog or digital hardware implementations.


    O (S)


    S is the sum of the elements of the array. Each ball moves individually, and do not roll groups of balls at the same time. Adequate complexity assessment for implementation in programming languages.

    Memory difficulty


    It leaves much to be desired. Bead sort is a record holder for extravagance - the cost of additional memory is many times higher than the cost of storing the array itself and averages O (n 2 ) .

    Physics



    The presence or absence of balls can be interpreted as analog voltage passing through a series of electrical resistors. The rods along which the balls move are analogues of electrical resistors , the voltage in which increases from top to bottom.

    Do not kick for the tongue-tied use of electrical engineering terms, I had a triple with plus four and minus in my physics school .

    I send experts of electrostatics for details in this pdf-document .

    In fact


    Bead sort is a type of counting sort . The number of balls in each vertical track is the number of elements in the array equal to or greater than the serial number of the vertical.

    Algorithm Characteristics


    TitleBead sorting; Abacus sort
    The authorsJoshua J. Arulanandam, Christian S. Calud, Michael J. Dinin
    Year of publication2002
    ClassDistribution Sort
    SustainabilitySustainable
    ComparisonsNo comparisons
    Time complexityO (1)O (√n)O (n)O (S)
    Memory difficultyO (n 2 )

    References

    Bead sorting on the University of Auckland website
    Authors documentation on the algorithm, pdf
    Implementation on various PL
    Bead sort in the English Wikipedia

    Authors home pages:

    Joshua J. Arulanandham
    Christian S. Kalud
    Michael J. Dinin

    Also popular now: