Sorting algorithms/Bead sort: Difference between revisions
(WP link, added header) |
m (→C++: indentation) |
||
Line 4: | Line 4: | ||
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. |
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. |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
⚫ | |||
⚫ | |||
⚫ | |||
//O(2n) time complexity where n is the summation of the whole list to be sorted. |
//O(2n) time complexity where n is the summation of the whole list to be sorted. |
||
//O(3n) space complexity. |
//O(3n) space complexity. |
||
Line 15: | Line 13: | ||
void distribute( int dist, vector<int> &List)//*beads* go down into different buckets using gravity (addition). |
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 |
|||
} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
int main() |
int main() |
||
{ |
|||
⚫ | |||
vector<int> list; |
|||
⚫ | |||
int myints[] = {5,3,1,7,4,1,1}; |
|||
vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) ); |
vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) ); |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
</lang> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
===Output:=== |
===Output:=== |
Revision as of 12:24, 25 August 2010
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