w3resource

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;

// Function to distribute beads in the beadSort algorithm
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]++;
}

// Bead sort algorithm implementation
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
1. Beads falling down: 

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
2. Beads right side up: 
Sorted list/array: 142 43 36 32 25 12 7 6 4 4 1 1 

Flowchart:

Flowchart: Sort an array of positive integers using the Bead sort algorithm

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to sort the values of three variables which contain any value (numbers and/or literals).
Next: Write a C++ program to sort a list of numbers using Bogosort algorithm.

What is the difficulty level of this exercise?



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/cpp-exercises/sorting-and-searching/cpp-sorting-and-searching-exercise-2.php