Bucket Sort in C++

Bucket Sort in C++ is a sorting algorithm that is used to sort an array of data in an efficient and time-saving manner. It is a comparison sorting algorithm and is based on the divide and conquer technique. Bucket Sort is often used to sort larger data sets, as it is considered to be one of the most efficient sorting algorithms in terms of time complexity. In this article, we will discuss the details of Bucket Sort in C++ and its time and space complexity.

What is a Bucket Sort?

Bucket Sort is a sorting algorithm that is used to sort an array of data. It is based on the divide and conquer technique, which divides the data into a number of “buckets” or “bins” which are then sorted individually. The data is then reassembled in order from the individual buckets.

The algorithm works by dividing the data into a number of buckets, each with a different range of values. The data is then sorted into each bucket, and then the buckets are merged back together in order, creating a sorted data set.

Bucket Sort is a comparison sorting algorithm, meaning it compares the values of two elements in the data set in order to determine their order. It is considered to be one of the most efficient sorting algorithms in terms of time complexity and is often used to sort larger data sets.

How Does Bucket Sort Work?

Bucket Sort works by first dividing the data set into a number of “buckets” or “bins”. Each bucket contains elements with similar values. The data is then sorted within each bucket, and then the buckets are merged together in order, creating a sorted data set.

To illustrate how Bucket Sort works, let’s consider an example. Consider an array of size 8, containing the numbers 4, 5, 6, 7, 8, 9, 10, 11.

First, the array is divided into buckets, which in this case would be two buckets – one containing the numbers 4, 5, 6, 7, and the other containing 8, 9, 10, 11.

The data is then sorted within each bucket. In the first bucket, the numbers 4, 5, 6, 7 are sorted in ascending order, becoming 4, 5, 6, 7. In the second bucket, the numbers 8, 9, 10, 11 are also sorted in ascending order, becoming 8, 9, 10, 11.

The sorted buckets are then merged together, creating a sorted data set. The merged data set is 4, 5, 6, 7, 8, 9, 10, 11.

Time Complexity

The time complexity of Bucket Sort is dependent on the number of buckets used and the sorting technique used within each bucket.

The best-case time complexity of Bucket Sort is O(n), which means that the algorithm will take the same amount of time regardless of the size of the data set. This is because the data is divided into buckets, and the time taken to sort elements within each bucket is constant.

The average-case time complexity of Bucket Sort is O(n + k), where n is the size of the data set and k is the number of buckets. This is because the data is divided into buckets, and the time taken to sort elements within each bucket is constant.

The worst-case time complexity of Bucket Sort is O(n^2). This is because in the worst case, the buckets may not be evenly distributed and the data set may be unevenly sorted within each bucket.

Space Complexity

The space complexity of Bucket Sort is O(n + k), where n is the size of the data set and k is the number of buckets. This is because the data is divided into buckets, and each bucket requires a certain amount of space in order to store the elements.

C++ Implementation

Let’s look at an example of how to implement Bucket Sort in C++.

// Function to sort arr[] of size n using bucket sort 
void bucketSort(int arr[], int n) 
{ 
	// 1) Create n empty buckets 
	vector<int> b[n]; 
	
	// 2) Put array elements in different buckets 
	for (int i=0; i<n; i++) 
	{ 
	int bi = n*arr[i]; // Index in bucket 
	b[bi].push_back(arr[i]); 
	} 

	// 3) Sort individual buckets 
	for (int i=0; i<n; i++) 
		sort(b[i].begin(), b[i].end()); 

	// 4) Concatenate all buckets into arr[] 
	int index = 0; 
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < b[i].size(); j++) 
		arr[index++] = b[i][j]; 
} 

In this code, we use an array to store the buckets. The elements of the array are then sorted and merged into a single array.

Conclusion

In this article, we discussed Bucket Sort in C++. We looked at how the algorithm works and its time and space complexity. We also saw an example of how to implement the algorithm in C++. Bucket Sort is an efficient sorting algorithm and is often used to sort large data sets.

Exercises

#include <iostream>
#include <vector>
using namespace std;

// Function to sort arr[] of size n using bucket sort 
void bucketSort(int arr[], int n) 
{ 
	// 1) Create n empty buckets 
	vector<int> b[n]; 
	
	// 2) Put array elements in different buckets 
	for (int i=0; i<n; i++) 
	{ 
	int bi = n*arr[i]; // Index in bucket 
	b[bi].push_back(arr[i]); 
	} 

	// 3) Sort individual buckets 
	for (int i=0; i<n; i++) 
		sort(b[i].begin(), b[i].end()); 

	// 4) Concatenate all buckets into arr[] 
	int index = 0; 
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < b[i].size(); j++) 
		arr[index++] = b[i][j]; 
} 

// Main function 
int main() 
{ 
	int arr[] = {4, 5, 6, 7, 8}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	bucketSort(arr, n); 

	cout << "Sorted array is \n"; 
	for (int i=0; i<n; i++) 
	cout << arr[i] << " "; 
	return 0; 
} 

#include <iostream>

// Function to find the time complexity of Bucket Sort 
void bucketSortTimeComplexity(int n) 
{ 
	// Time complexity of Bucket Sort is O(n + k), 
	// where n is the size of the data set and 
	// k is the number of buckets 
	int k = 10; 
	int time_complexity = n + k; 
	
	std::cout << "The time complexity of Bucket Sort for an array of size " << n << " is " << time_complexity << std::endl; 
} 

// Main function 
int main() 
{ 
	int n = 10; 
	bucketSortTimeComplexity(n); 
	return 0; 
} 

#include <iostream>

// Function to find the space complexity of Bucket Sort 
void bucketSortSpaceComplexity(int n) 
{ 
	// Space complexity of Bucket Sort is O(n + k), 
	// where n is the size of the data set and 
	// k is the number of buckets 
	int k = 10; 
	int space_complexity = n + k; 
	
	std::cout << "The space complexity of Bucket Sort for an array of size " << n << " is " << space_complexity << std::endl; 
} 

// Main function 
int main() 
{ 
	int n = 10; 
	bucketSortSpaceComplexity(n); 
	return 0; 
} 

#include <iostream>
#include <vector>
using namespace std;

// Function to sort arr[] of size n using bucket sort 
void bucketSort(int arr[], int n) 
{ 
	// 1) Create n empty buckets 
	vector<int> b[n]; 
	
	// 2) Put array elements in different buckets 
	for (int i=0; i<n; i++) 
	{ 
	int bi = n*arr[i]; // Index in bucket 
	b[bi].push_back(arr[i]); 
	} 

	// 3) Sort individual buckets 
	for (int i=0; i<n; i++) 
		sort(b[i].begin(), b[i].end()); 

	// 4) Concatenate all buckets into arr[] 
	int index = 0; 
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < b[i].size(); j++) 
		arr[index++] = b[i][j]; 
} 

// Main function 
int main() 
{ 
	int arr[] = {4, 5, 6, 7, 8, 9, 10, 11}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	bucketSort(arr, n); 

	cout << "Sorted array is \n"; 
	for (int i=0; i<n; i++) 
	cout << arr[i] << " "; 
	return 0; 
} 

#include <iostream>

// Function to find the average-case time complexity of Bucket Sort 
void bucketSortAverageCaseTimeComplexity(int n) 
{ 
	// Average-case time complexity of Bucket Sort is O(n + k), 
	// where n is the size of the data set and 
	// k is the number of buckets 
	int k = 8; 
	int time_complexity = n + k; 
	
	std::cout << "The average-case time complexity of Bucket Sort for an array of size " << n << " is " << time_complexity << std::endl; 
} 

// Main function 
int main() 
{ 
	int n = 8; 
	bucketSortAverageCaseTimeComplexity(n); 
	return 0; 
}