Problem Statement

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.

Let's start with the solution:

bead=: [: +/ #"0&1


   bead bead 2 4 1 3 3
4 3 3 2 1
   bead bead 5 3 1 7 4 1 1
7 5 4 3 1 1 1


bball=: ] (] + [: bead^:2 -) <./ - 1:


   bball 2 0 _1 3 1 _2 _3 0
3 2 1 0 0 _1 _2 _3