# Implementation of Bucket Sort in Java

16

Title: Implementation of Bucket Sort in Java

Data, data everywhere, but in what order?! Fear not, for amidst the chaos stands Bucket Sort, a valiant algorithm ready to bring structured serenity. Today, we delve into its depths, implementing it in Java, exploring its logic, and conquering unordered lists with confidence. Buckle up, and let’s sort some buckets!

## Bucket Sort: Dividing and Conquering Chaos

At its core, Bucket Sort visualizes the data as a collection of pebbles scattered across a beach. Its strategy? Gather the pebbles into buckets based on size, sort each bucket efficiently, and voila, the beach is neat and tidy! Translated to code, it works like this:

1. Create Buckets: Imagine buckets lined up, each representing a range of values.
2. Distribute Pebbles: Categorize each data item and toss it into its corresponding bucket.
3. Subdue Each Bucket: Within each bucket, apply a simple sorting algorithm like Insertion Sort.
4. Combine the Conquests: Gather the sorted pebbles from each bucket, one by one, to form the final ordered list.

## Implementation of Bucket Sort in Java

Here’s the basic structure of Bucket Sort in Java:

Java
``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BucketSort{

// Function to find the maximum value in the array
private static int findMax(int[] arr) {
int max = arr[0];  // Initialize max with the first element
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void bucketSort(int[] arr) {
// 1. Define the number of buckets and their ranges
int maxVal = findMax(arr);

// 2. Create and initialize buckets
List<Integer>[] buckets = new ArrayList[numBuckets];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new ArrayList<>();
}

// 3. Distribute elements into buckets
for (int element : arr) {
int bucketIndex = element / arr.length;
}

// 4. Sort each bucket
for (int i = 0; i < numBuckets; i++) {
Collections.sort(buckets[i]); // Insertion Sort or your preferred method
}

// 5. Combine sorted buckets into the original array
int index = 0;
for (List<Integer> bucket : buckets) {
for (int element : bucket) {
arr[index++] = element;
}
}
}

public static void main(String[] args) {
int[] array = {83, 24, 52, 16, 77};
System.out.println("Original Array: " + Arrays.toString(array));

bucketSort(array);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
}``````

## Code Snippets and Explanations

1. Bucket Creation:
Java
``````// Define the number of buckets and their ranges

// Create and initialize buckets
List<Integer>[] buckets = new ArrayList[numBuckets];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new ArrayList<>();
}
``````

This code dynamically defines the number of buckets based on the data’s maximum value and a chosen range. Each bucket is represented as an `ArrayList` to hold the elements within its range.

1. Distribution and Sorting:
Java
``````// Distribute elements into buckets
for (int element : arr) {
int bucketIndex = element / arr.length;
}

// Sort each bucket
for (int i = 0; i < numBuckets; i++) {
Collections.sort(buckets[i]); // Insertion Sort or your preferred method
}
``````

The elements are scattered into their respective buckets based on their calculated bucket index. Then, each bucket’s elements are sorted using `Collections.sort()` which employs Insertion Sort by default. You can choose other sorting algorithms for larger buckets.

### Examples: Putting Theory into Practice

Consider these unsorted arrays:

Example 1: `[83, 24, 52, 16, 77]`

the elements would be distributed as:

• Bucket 0: [16]
• Bucket 1: [24]
• Bucket 2: [52]
• Bucket 3: [77]
• Bucket 4: [83]

Sorting each bucket individually (e.g., using Insertion Sort) and then combining them results in the sorted array: `[16, 24, 52, 77, 83]`.

Example 2: Unsorted array: `[90, 23, 75, 41, 68]`

Bucket distribution:

• Bucket 0: [23]
• Bucket 1: [41]
• Bucket 2: [68]
• Bucket 3: [75]
• Bucket 4: [90]

Sorting each bucket (using Insertion Sort for illustration):

• Bucket 0: [23] (already sorted)
• Bucket 1: [41] (already sorted)
• Bucket 2: [68] (already sorted)
• Bucket 3: [75] (already sorted)
• Bucket 4: [90] (already sorted)

### Output:

Java
``````// Example 1
Original Array: [83, 24, 52, 16, 77]
Sorted Array: [16, 24, 52, 77, 83]

// Example 2
Original Array: [90, 23, 75, 41, 68]
Sorted Array: [23, 41, 68, 75, 90]``````

• Linear time complexity (O(n)) in the average and best cases, making it efficient for large datasets, especially when the data is uniformly distributed.
• Stable: Preserves the relative order of equal elements.
• Simple to understand and implement.

• Performance depends on choosing an appropriate range: Too few buckets can lead to inefficient sorting within buckets, while too many can create empty buckets and wasted space.
• Not as efficient as QuickSort or MergeSort for non-uniformly distributed data.

## Time and Space Complexity of Bucket Sort

### Conclusion:

Bucket Sort offers a valuable tool for sorting in Java, particularly when dealing with uniformly distributed data and needing good average-case performance. By understanding its logic and implementation, you can effectively bring order to your data buckets and conquer the chaos of unsorted lists!