﻿ C++ : Sort an array using the Bead sort algorithm

# C++ Bead sort algorithm Exercise: Sort an array of positive integers using the Bead sort algorithm

## C++ Sorting: Exercise-2 with Solution

Write a C++ program to sort an array of positive integers using the Bead sort algorithm.

Sample Solution:

C++ Code :

``````// Including necessary C++ libraries
#include <iostream>
#include <vector>

// Using specific items from the std namespace for convenience
using std::cout;
using std::vector;

void distribute(int dist, vector<int>&List) {
// If the required distribution exceeds the list size, resize the list
if (dist > List.size())
List.resize(dist);

// Increment values in the list for 'dist' positions
for (int i = 0; i < dist; i++)
List[i]++;
}

vector<int> beadSort(int *myints, int n) {
// Initializing necessary vectors and copying input values into 'fifth'
vector<int> list, list2, fifth(myints, myints + n);

// Displaying initial values before bead sorting
cout << "1. Beads falling down: ";
for (int i = 0; i < fifth.size(); i++)
distribute(fifth[i], list);
cout << '\n';

cout << "\nBeads on their sides: ";
for (int i = 0; i < list.size(); i++)
cout << " " << list[i];
cout << '\n';

// Further sorting and displaying beads
cout << "2. Beads right side up: ";
for (int i = 0; i < list.size(); i++)
distribute(list[i], list2);
cout << '\n';

// Returning the sorted list after bead sorting
return list2;
}

// Main function
int main() {
// Initializing an array of integers for sorting
int myints[] = {36, 4, 1, 4, 25, 32, 12, 43, 142, 6, 7, 1};
cout << "Original array:\n";
// Displaying the original array values
for (int i = 0; i < sizeof(myints) / sizeof(int); i++)
cout << " " << myints[i];
cout << '\n';

// Sorting the array using the beadSort algorithm
vector<int> sorted = beadSort(myints, sizeof(myints) / sizeof(int));
cout << "Sorted list/array: ";
// Displaying the sorted list
for (unsigned int i = 0; i < sorted.size(); i++)
cout << sorted[i] << ' ';

// Returning 0 to indicate successful execution
return 0;
}
``````

Sample Output:

```Original array:
36 4 1 4 25 32 12 43 142 6 7 1

Beads on their sides:  12 10 10 10 8 8 7 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sorted list/array: 142 43 36 32 25 12 7 6 4 4 1 1
```

Flowchart:

C++ Code Editor: