Bucket Sort Using C++ [Easy Guide]

Filed Under: C++
Bucket Sort Using C

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.

Example
Example

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 Sort
Algorithm Bucket Sort

Output

Bucket Sort Output
Bucket 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

close
Generic selectors
Exact matches only
Search in title
Search in content