
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.




*        Bead Sort                 11/05/2016
BEADSORT CSECT
         USING  BEADSORT,R13       base register
SAVEAR   B      STM-SAVEAR(R15)    skip savearea
         DC     17F'0'             savearea 
STM      STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         " 
         ST     R15,8(R13)         " 
         LR     R13,R15            " 
         LA     R6,1               i=1
LOOPI1   CH     R6,=AL2(N)         do i=1 to hbound(z)
         BH     ELOOPI1            leave i
         LR     R1,R6                i
         SLA    R1,1                 <<1
         LH     R2,Z-2(R1)           z(i)
         CH     R2,LO                if z(i)<lo
         BNL    EIHO                 then
         STH    R2,LO                  lo=z(i)
EIHLO    CH     R2,HI                if z(i)>hi
         BNH    EIHHI                then  
         STH    R2,HI                  hi=z(i)
EIHHI    LA     R6,1(R6)           iterate i
         B      LOOPI1             next i
ELOOPI1  LA     R9,1               1
         SH     R9,LO              -lo+1
         LA     R6,1               i=1
LOOPI2   CH     R6,=AL2(N)         do i=1 to hbound(z)
         BH     ELOOPI2            leave i
         LR     R1,R6                i
         SLA    R1,1                 <<1
         LH     R3,Z-2(R1)           z(i)
         AR     R3,R9                z(i)+o
         IC     R2,BEADS-1(R3)       beads(l)
         LA     R2,1(R2)             beads(l)+1
         STC    R2,BEADS-1(R3)       beads(l)=beads(l)+1
         LA     R6,1(R6)           iterate i
         B      LOOPI2             next i
ELOOPI2  SR     R8,R8              k=0
         LH     R6,LO              i=lo
LOOPI3   CH     R6,HI              do i=lo to hi
         BH     ELOOPI3            leave i
         LA     R7,1                 j=1
         SR     R10,R10              clear r10
         LR     R1,R6                i
         AR     R1,R9                i+o
         IC     R10,BEADS-1(R1)      beads(i+o)
LOOPJ3   CR     R7,R10               do j=1 to beads(i+o)
         BH     ELOOPJ3              leave j
         LA     R8,1(R8)               k=k+1
         LR     R1,R8                  k
         SLA    R1,1                   <<1
         STH    R6,S-2(R1)             s(k)=i
         LA     R7,1(R7)             iterate j
         B      LOOPJ3               next j
ELOOPJ3  AH     R6,=H'1'           iterate i
         B      LOOPI3             next i
ELOOPI3  LA     R7,1               j=1
LOOPJ4   CH     R7,=H'2'           do j=1 to 2
         BH     ELOOPJ4            leave j
         CH     R7,=H'1'             if j<>1
         BE     ONE                  then
         MVC    PG(7),=C'sorted:'      zap
ONE      LA     R10,PG+7             pgi=@pg+7
         LA     R6,1                 i=1
LOOPI4   CH     R6,=AL2(N)           do i=1 to hbound(z)
         BH     ELOOPI4              leave i
         CH     R7,=H'1'               if j=1
         BNE    TWO                    then
         LR     R1,R6                    i
         SLA    R1,1                     <<1
         LH     R11,Z-2(R1)              zs=z(i)
         B      XDECO                  else
TWO      LR     R1,R6                    i
         SLA    R1,1                     <<1
         LH     R11,S-2(R1)              zs=s(i)
XDECO    XDECO  R11,XDEC               edit zs
         MVC    0(6,R10),XDEC+6        output zs
         LA     R10,6(R10)             pgi=pgi+6
         LA     R6,1(R6)             iterate i
         B      LOOPI4               next i
ELOOPI4  XPRNT  PG,80                print buffer
         LA     R7,1(R7)             iterate j
         B      LOOPJ4             next j
ELOOPJ4  L      R13,4(0,R13)       epilog
         LM     R14,R12,12(R13)    "
         XR     R15,R15            "
         BR     R14                "
         LTORG                     literal table
N        EQU    (S-Z)/2            number of items
Z        DC     H'5',H'3',H'1',H'7',H'-1',H'4',H'9',H'-12'
         DC     H'2001',H'-2010',H'17',H'0'
S        DS     (N)H               s same size as z
LO       DC     H'32767'           2**31-1
HI       DC     H'-32768'          -2**31
PG       DC     CL80'   raw:'      buffer
XDEC     DS     CL12               temp
BEADS    DC     4096X'00'          beads
         YREGS
         END    BEADSORT