
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Task

Sort an array of positive integers using the Bead Sort Algorithm.

A   bead sort   is also known as a   gravity sort.



Algorithm has   O(S),   where   S   is the sum of the integers in the input set:   Each bead is moved individually.

This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations.




/*REXX program sorts a list (four groups)  of integers  using the  bead sort  algorithm.*/
                                 /* [↓]  define  two dozen  grasshopper  numbers.       */
gHopper= 1 4 10 12 22 26 30 46 54 62 66 78 94 110 126 134 138 158 162 186 190 222 254 270
                                 /* [↓]  these are also called hexagonal pyramidal #s.  */
greenGrocer=  0 4 16 40 80 140 224 336 480 660 880 1144 1456 1820 2240 2720 3264 3876 4560
                                 /* [↓]  define twenty-three Bernoulli numerator numbers*/
bernN= '1 -1 1 0 -1 0 1 0 -1 0 5 0 -691 0 7 0 -3617 0 43867 0 -174611 0'
                                 /* [↓] also called the Reduced Totient function, and is*/
                                 /*also called Carmichael lambda, or the LAMBDA function*/
psi=      1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20 12 18 6 28 4 30 8 10 16
y= gHopper greenGrocer bernN psi                 /*combine the four lists into one list.*/
call show  'before sort',  y                     /*display the  list  before sorting.   */
say copies('░', 75)                              /*show long separator line before sort.*/
call show  ' after sort',  beadSort(y)           /*display the  list   after sorting.   */
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
beadSort: procedure; parse arg low . 1 high . 1 z,$;  @.=0 /*$:  the list to be sorted. */
            do j=1  until z=='';    parse var  z   x  z    /*pick the meat off the bone.*/
            x= x / 1;               @.x= @.x + 1           /*normalize X;  bump counter.*/
            low= min(low, x);       high= max(high, x)     /*track lowest and highest #.*/
            end   /*j*/
                                                           /* [↓] now, collect the beads*/
            do m=low  to high;      if @.m>0  then $= $ copies(m' ', @.m)
            end   /*m*/
          return $
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: parse arg txt,y;   z= words(y);                       w= length(z)
            do k=1  for z; say right('element',30)  right(k,w)  txt":"  right(word(y,k),9)
            end   /*k*/
      return