3

Bucket Sort Using C++ [Easy Guide]

 2 years ago
source link: https://www.journaldev.com/58999/bucket-sort-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In this article, we will code bucket sort using C++. Bucket sort is a popular interview problem often asked by the top recruiters. We will first look at the problem statement and then move to the concept of this algorithm. So without any further delay, let’s see the details of this algorithm.

What Is Bucket Sort?

This sorting method is used for declaring the ranks of candidates who took part in some competition. This is because a candidate’s score may lie in any interval between 0 – 100. You have a list of students with their names and their scores. Suppose there are a million candidates like these. Our task is to sort these students based on their marks.

Note: We use bucket sort whenever the data is bounded.

The example given below will help you understand the concept better.

ExampleExample

Concept of the Bucket Sort Algorithm

To code this algorithm, we have to create an array of buckets(buckets represent containers). Each of these buckets stores the information of various candidates. To represent a single bucket, we use a vector. And similarly to represent an array of buckets we use a two-dimensional array.

  • Once the array is ready, start filling the students into the buckets.
  • Let the index of each bucket denote the score it will hold.
  • Suppose candidate “X” has a score of 57, then it will be put into the bucket at the index 57. But if another candidate say “Y” has the same score.
  • To represent a candidate, we will create a class with data member: marks and name.
  • Now pass the array of candidates to bucket_sort() function.
  • Create another array “v” of the type candidate and size 101, assuming that the marks are in the range 0 to 100.
  • We will iterate over the entire candidates array.
  • Then we will see the marks of each candidate.
    • int marks = candidate[i].marks
  • Now push the student into correct location in array “v”.
    • v[m].push_back(candidate[i])
  • Now, we have successfully inserted the candidates at their correct positions.
  • If you want to print the toppers first, we can simply reverse the array “v” or adjust the iteration accordingly.

So, we are done with the algorithm. Let’s quickly dive into the code and test it.

Implementing the Bucket Sort Algorithm Using C++

Let’s now implement the bucket sort algorithm in C++ and see how the output sorts out the lists.

#include <iostream>
#include <vector>
using namespace std;
// class to represent each candidate
class Candidate
{
// data members are public
// to allow foreign access
public:
int marks;
string name;
// default constructor
Candidate(string name, int marks): name(name), marks(marks) {}
};
void bucket_sort(vector <Candidate> candidates)
{
// assuming the marks are in the range
// 0 to 100
vector <Candidate> v[101];
// iterate over the candidates vector
for(int i = 0; i < candidates.size(); i++)
{
int marks = candidates[i].marks;
v[marks].push_back(candidates[i]);
}
// now print the v vector accordingly
for(int i = 100; i >= 0; i--)
for(Candidate cand : v[i])
cout << "Name:" << cand.name << " Marks: " << cand.marks << endl;
}
int main()
{
cout << "Enter the total number of candidates" << endl;
int n;
cin >> n;
cout << "Enter the details of the candidates" << endl;
vector <Candidate> candidates;
while(n--)
{
string name;
int marks;
cin >> name >> marks;
Candidate temp(name, marks);
candidates.push_back(temp);
}
// input is complete, now run the function
bucket_sort(candidates);
}
Algorithm Bucket SortAlgorithm Bucket Sort

Output

Bucket Sort OutputBucket Sort Output

Conclusion

In this article, we used several concepts to code an algorithm for bucket sort. In the beginning, we discussed the outcome and the concept of this sorting method. Then we moved to the algorithm part and in the end, we wrote a C++ program to demonstrate this algorithm.

One more thing I would like to highlight is that the overall time complexity of this algorithm is linear i.e. O(N). This is because we are running through the candidates’ list only once. That’s all for today, thanks a lot for reading.

Further Readings

To learn more about sorting methods, you can visit the following websites.

https://www.journaldev.com/56329/merge-sort-in-cpp

https://www.journaldev.com/58641/wave-sort-using-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK