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:
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
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.
- include<iostream>
- 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
{header|J}
<lang j>bead=: [: +/ #"0&1</lang>
Example use:
<lang> bead bead 2 4 1 3 3 4 3 3 2 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
}
- Demonstration code
puts [beadsort {5 3 1 7 4 1 1}]</lang> Output:
7 5 4 3 1 1 1