Implementation of Bucket Sort in Java

By
Shivam Gupta
-
12
Implementation of Bucket Sort in Java
Advertisement

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);
        int numBuckets = (maxVal / arr.length) + 1; // Adjust range based on your data spread

        // 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;
            buckets[bucketIndex].add(element);
        }

        // 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
int numBuckets = (maxVal / arr.length) + 1; // Adjust range based on your data spread

// 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;
    buckets[bucketIndex].add(element);
}

// 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]

Advantages of Bucket Sort:

  • 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.

Disadvantages of Bucket Sort:

  • 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.

Complexity:

Time and Space Complexity of Bucket Sort

ComplexityBest CaseAverage CaseWorst Case
TimeO(n + k)O(n + k)O(n^2)
SpaceO(n + k)O(n + k)O(n + k)

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!

Additional Notes:

  • This blog post focused on Bucket Sort with numerical data. It can be adapted for string data using appropriate hashing functions.
  • Libraries like Apache Commons Lang provide optimized Bucket Sort implementations.
  • Explore other sorting algorithms like QuickSort and MergeSort to compare their strengths and weaknesses for different data scenarios.

Remember, the key to mastering any algorithm is practice and understanding. So, grab your data buckets, dive into the code, and conquer the sorting challenges that await!

Latest Posts:

RELATED ARTICLESMORE FROM AUTHOR