
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.




 
#lang QB64
'***************************************************
'* BeadSort is VERY fast for small CGSortLibArray(max)-CGSortLibArray(min). Typical performance is
'* O(NlogN) or better. However as the key values (array values and ranges) go up, the performance
'* drops steeply excellent for small-ranged arrays. Integer only at this point.  Throughput is
'* roughly 900k/GHzS for double-precision, with binary range (0,1). Related to CountingSort()
'***************************************************
SUB BeadSort (CGSortLibArray() AS DOUBLE, start AS LONG, finish AS LONG, order&)
    DIM MAX AS DOUBLE: MAX = CGSortLibArray(start)
    DIM BeadSort_Sum AS DOUBLE
    DIM BeadSort_I AS LONG
    DIM BeadSort_J AS LONG
    FOR BeadSort_I = start + 1 TO (finish - start)
        IF (CGSortLibArray(BeadSort_I) > MAX) THEN MAX = CGSortLibArray(BeadSort_I)
    NEXT
    REDIM beads((finish - start), MAX)
    FOR BeadSort_I = 0 TO (finish - start) - 1
        FOR BeadSort_J = 0 TO CGSortLibArray(BeadSort_I) - 1
            beads(BeadSort_I, BeadSort_J) = 1
        NEXT
    NEXT
    IF order& = 1 THEN
        FOR BeadSort_J = 0 TO MAX
            BeadSort_Sum = 0
            FOR BeadSort_I = 0 TO (finish - start)
                BeadSort_Sum = BeadSort_Sum + beads(BeadSort_I, BeadSort_J)
                beads(BeadSort_I, BeadSort_J) = 0
            NEXT
            FOR BeadSort_I = (finish - start) - BeadSort_Sum TO (finish - start)
                beads(BeadSort_I, BeadSort_J) = 1
            NEXT
        NEXT
        FOR BeadSort_I = 0 TO (finish - start)
            BeadSort_J = 0
            WHILE BeadSort_J < MAX AND beads(BeadSort_I, BeadSort_J)
                BeadSort_J = BeadSort_J + 1
            WEND
            CGSortLibArray(BeadSort_I) = BeadSort_J
        NEXT
    ELSE
        FOR BeadSort_J = MAX TO 0 STEP -1
            BeadSort_Sum = 0
            FOR I = 0 TO (finish - start)
                BeadSort_Sum = BeadSort_Sum + beads(I, BeadSort_J)
                beads(I, BeadSort_J) = 0
            NEXT
            FOR I = (finish - start) TO (finish - start) - BeadSort_Sum STEP -1
                beads(I, BeadSort_J) = 1
            NEXT
        NEXT
        FOR BeadSort_I = 0 TO (finish - start)
            BeadSort_J = 0
            WHILE BeadSort_J < MAX AND beads(BeadSort_I, BeadSort_J)
                BeadSort_J = BeadSort_J + 1
            WEND
            CGSortLibArray(finish - BeadSort_I) = BeadSort_J
        NEXT
    END IF
END SUB
 