“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022.”

Bucket sort, also known as box sort, works by sorting an array into a finite number of buckets. Each bucket is sorted, maybe using some other sort algorithm or using bucket sort recursively, bucket sort is a generalization of pigeon nest sort.

Bucket sorting works great when the input is evenly distributed over a range.

Example: Sort a large number of floating point numbers ranging from 0.0 to 1.0 evenly distributed within that range.

To create a bucket algorithm:

1. Create n empty buckets (list).
2. Insert bucket[n*array[I]] for each array element arr[I]
3. Sort each bucket using insert sort
4. Connect all sort buckets

Java example:

import java.util.*;
import java.util.Collections;

class GFG {

	// Use bucket sort to sort arr[] of size n
	static void bucketSort(float arr[], int n)
	{
		if (n <= 0)
			return;

		// 1) Create n empty buckets
		@SuppressWarnings("unchecked")
		Vector<Float>[] buckets = new Vector[n];

		for (int i = 0; i < n; i++) {
			buckets[i] = new Vector<Float>();
		}

		// 2) Put the array elements in different buckets
		for (int i = 0; i < n; i++) {
			float idx = arr[i] * n;
			buckets[(int)idx].add(arr[i]);
		}

		// 3) Sort a single bucket
		for (int i = 0; i < n; i++) {
			Collections.sort(buckets[i]);
		}

		// 4) Connect all buckets to arR []
		int index = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < buckets[i].size(); j++) {
				arr[index++] = buckets[i].get(j);
			}
		}
	}

	public static void main(String args[])
	{
		float arr[] = { (float)0.897, (float)0.565,
						(float)0.656, (float)0.1234,
						(float)0.665, (float)0.3434 };

		int n = arr.length;
		bucketSort(arr, n);

		System.out.println("The sorted array is");
		for (float el : arr) {
			System.out.print(el + ""); }}}Copy the code

The output

The sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897Copy the code

performance

Time complexity: If we assume O(1) time to insert into the bucket, then steps 1 and 2 of the above algorithm obviously require O(n) time. O(1) is easy to implement if we use linked lists to represent buckets. Step 4 also takes O(n) time because there will be n items in all buckets. The main step of analysis is step 3. If all the numbers are evenly distributed, this step also takes O(n) time on average.

Where there are negative numbers

The above example is bucket sorting, sorting an array greater than zero. For negative numbers, use the following method.

1. Create two empty vectors Neg[], Pos[] (positive and negative, respectively) by converting all negative elements in Neg[] to positive (Neg[I] = -1 * Arr[I]), Store all +ve at pos[] (pos[I] = Arr[I])
2. BucketSortPositive (Pos, pos.size()) bucketSortPositive(Neg, neg.size ()), bucketSortPositive(arr[], n)
3. Create n empty buckets (or lists).
4. Insert each array arr[I] into bucket[n*array[I]]
5. Sort individual buckets using insert sort.
6. Connect all sorted buckets.

Java example

import java.util.*;
class GFG
{

// Use bucket sort to sort arr[] of size n
static void bucketSort(Vector<Double> arr, int n)
{

	// 1) Create n empty buckets
	@SuppressWarnings("unchecked")
	Vector<Double> b[] = new Vector[n];
	for (int i = 0; i < b.length; i++)
	b[i] = new Vector<Double>();

	// 2) Put the array elements in different buckets
	for (int i = 0; i < n; i++)
	{
	int bi = (int)(n*arr.get(i)); // Index in bucket
	b[bi].add(arr.get(i));
	}

	// 3) Sort a single bucket
	for (int i = 0; i < n; i++)
	Collections.sort(b[i]);

	// 4) Connect all buckets to arR []
	int index = 0;
	arr.clear();
	for (int i = 0; i < n; i++)
	for (int j = 0; j < b[i].size(); j++)
		arr.add(b[i].get(j));
}

// This function splits the array in two and calls bucketSort() on both arrays.
static void sortMixed(double arr[], int n)
{
	Vector<Double>Neg = new Vector<>();
	Vector<Double>Pos = new Vector<>();

	// Iterate over the array of elements
	for (int i = 0; i < n; i++)
	{
	if (arr[i] < 0)

		// Store -ve elements by converting them to +ve elements
		Neg.add (-1 * arr[i]) ;
	else

		// Store the +ve element
		Pos.add (arr[i]) ;
	}
	bucketSort(Neg, (int)Neg.size());
	bucketSort(Pos, (int)Pos.size());

	// First store the elements of the Neg[] array by converting to -ve
	for (int i = 0; i < Neg.size(); i++)
	arr[i] = -1 * Neg.get( Neg.size() -1 - i);

	/ / sorting
	for(int j = Neg.size(); j < n; j++)
	arr[j] = Pos.get(j - Neg.size());
}

public static void main(String[] args)
{
	double arr[] = {-0.897.0.565.0.656,
					-0.1234.0.0.3434};
	int n = arr.length;
	sortMixed(arr, n);

	System.out.print("Sorted array: \n");
	for (int i = 0; i < n; i++)
	System.out.print(arr[i] + "");
}0
}
Copy the code

Output: **

-0.897 -0.1234 0 0.3434 0.565 0.656Copy the code