Sorting algorithms/Bead sort

Sorting algorithms/Bead sort
You are encouraged to solve this task according to the task description, using any language you may know.

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 log²n) sorts
Shell Sort

O(n²) 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

In this task, the goal is to sort an array of positive integers using the Bead Sort Algorithm.

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.

C

A rather straightforward implementation; since we do not use dynamic matrix, we have to know the maximum value in the array in advance. Using no sparse matrix means the matrix needs MAX*MAX times the size of an integer bytes to be stored.

<lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <stdbool.h>
3. include <string.h>

int *bead_sort(int *a, size_t len) {

 size_t i, j, k;
 bool fallen;
 int *t, *r = NULL;
 int max = a[0];

 for(i = 1; i < len; i++) 
 {
   if ( a[i] < 0 ) return NULL;  // we can't sort nums < 0
   if ( max < a[i] ) max = a[i];
 }
 
 t = malloc(max*max*sizeof(int));
 if ( t == NULL ) return NULL;
 memset(t, 0, max*max*sizeof(int));

 r = malloc(len*sizeof(int));
 memset(r, 0, len*sizeof(int));
 if (r != NULL) 
 {
   // "split" numbers into "beads" (units)
   for(i = 0; i < len; i++)
   {
     for(j = 0; j < a[i]; j++) t[i*max + j]++;
   }

   // make them fall down
   do
   {
     fallen = false;
     for(i = 0; i < max-1; i++)
     {

for(j = 0; j < max; j++) { if ( t[i*max + j] == 1 && t[(i+1)*max + j] == 0 ) { fallen = true; t[i*max + j] = 0; t[(i+1)*max + j] = 1; } }

     }
   } while(fallen);

1. if defined(SHOW_BEADS)

   for(i = 0; i < max; i++)
   {
     for(j = 0; j < max; j++)
     {

printf("%d ", t[i*max + j]);

     }
     printf("\n");
   }

1. endif

   // count beads
   k = 0;
   for(i = 0; i < max; i++)
   {
     if ( t[(max - i - 1)*max + 0] == 0 ) break;
     for(j = 0; j < max; j++)
     {

int v = t[(max - i - 1)*max + j]; if ( v == 0 ) break; r[k] += v;

     }
     k++;
   }
   
 }
 free(t);
 return r;

}

int main() {

 int values[] = {5, 3, 1, 7, 4, 1, 1, 20};
 size_t i, len = sizeof(values)/sizeof(int);

 int *r = bead_sort(values, len);
 if ( r == NULL ) return EXIT_FAILURE;

 for(i = 0; i < len; i++)
 {
   printf("%d ", r[i]);
 }
 putchar('\n');

 free(r);
 return EXIT_SUCCESS;

}</lang>

C++

<lang cpp>//this algorithm only works with positive, whole numbers. //O(2n) time complexity where n is the summation of the whole list to be sorted. //O(3n) space complexity.

1. include<iostream>
2. include<vector>

using namespace std;

void distribute( int dist, vector<int> &List)//*beads* go down into different buckets using gravity (addition). {

   if (dist > List.size() )
       List.resize(dist,0); //resize if too big for current vector

   for (int i=0; i < dist; i++)
       List[i] = List[i]+1;

}

int main() {

   vector<int> list;
   vector<int> list2;
   int myints[] = {5,3,1,7,4,1,1};
   vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

   cout << "#1 Beads falling down: ";
   for (int i=0; i < fifth.size(); i++)
       distribute (fifth[i], list);
   cout << endl;

   cout <<endl<< "Beads on their sides: ";
   for (int i=0; i < list.size(); i++)
       cout << " " << list[i];
   cout << endl;	

   //second part

   cout << "#2 Beads right side up: ";
   for (int i=0; i < list.size(); i++)
       distribute (list[i], list2);
   cout << endl;

   cout <<endl<< "Sorted list/array";
   for (int i=0; i < list2.size(); i++)
       cout << " " << list2[i];
   cout << endl;
   return 0;

}</lang>

Output:

Beads falling down:

Beads on their sides: 7 4 4 3 2 1 1 Beads right side up:

Sorted list/array 7 5 4 3 1 1 1

Haskell

<lang haskell>import Data.List

beadSort :: [Int] -> [Int] beadSort = map sum. transpose. transpose. map (flip replicate 1)</lang> Example; <lang haskell>*Main> beadSort [2,4,1,3,3] [4,3,3,2,1]</lang>

J

<lang j>bead=: [: +/ #"0&1</lang>

Example use:

<lang> 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</lang>

Tcl

<lang tcl>package require Tcl 8.5

proc beadsort numList {

   # Special case: empty list is empty when sorted.
   if {![llength $numList]} return
   # Set up the abacus...
   foreach n $numList {

for {set i 0} {$i<$n} {incr i} { dict incr vals $i }

   }
   # Make the beads fall...
   foreach n [dict values $vals] {

for {set i 0} {$i<$n} {incr i} { dict incr result $i }

   }
   # And the result is...
   dict values $result

}

1. Demonstration code

puts [beadsort {5 3 1 7 4 1 1}]</lang> Output:

7 5 4 3 1 1 1