Bucket Sort

                  Bucket Sort

geeksforgeeks

hackerearth

visualization

Time Complexity: If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time. The O(1) is easily possible if we use a linked list to represent a bucket (In the following code, C++ vector is used for simplicity). Step 4 also takes O(n) time as there will be n items in all buckets.

	#include<bits/stdc++.h>
	using namespace std;
	void bucketSort(float ar[], int n)
	{
	vector<float> b[n];
	for(int i = 0; i < n; i++){
	int bi = n*ar[i]; // index of bucket.
	b[bi].push_back(ar[i]);
	}
	// sort individual buckets
	for(int i = 0; i < n; i++)
	sort(b[i].begin(), b[i].end());
	int idx = 0;
	for(int i = 0; i < n; i++){
	for(int j = 0; j < b[i].size(); j++){
	ar[idx++] = b[i][j];
	}
	}
	}
	void print(float a[], int n)
	{
	for(int i = 0 ; i < n; i++)
	cout << a[i] << " ";
	cout << endl;
	}
	int main()
	{
	float ar[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
	int n = sizeof(ar)/sizeof(ar[0]);
	bucketSort(ar, n);
	print(ar, n);
	return 0;
	}

view raw bucket.cpp hosted with ❤ by GitHub

Share: