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++

<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