The bead-sorting algorithm orders a list of a positive integers increasingly by representing numbers as a list of a 1s, where each 1 stands for a bead. The k initial integers to be sorted are initially represented as left-aligned rows of beads, and in each step of the sorting process, a bead is slid down one unit if possible until each bead can no longer slide. For example, the graphic above shows the process for the numbers 7, 2, 1, 4, and 2 (Trott 2004, pp. 82-83).

Explore with Wolfram|Alpha


Arulanandham, J. J.; Calude, C. S.; and Dinneen, M. J. "Bead-Sort: a Natural Sorting Algorithm." Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, No. 76, 153-162, 2002.Arulanandham, J. J.; Calude, C. S.; Dinneen, M. J.; and Peper, F. (Eds.). Unconventional Models of Computation: Third International Conference, UMC 2002, Kobe, Japan, October 15-19, 2002, Proceedings. Berlin: Springer-Verlag, 2002.Trott, M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, pp. 82-83, 2004.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Bead-Sort." From MathWorld--A Wolfram Web Resource.

Subject classifications