What is Bucket Sort?

Bucket Sort is a sorting method that divides an array into tiny buckets before sorting the elements within each bucket separately using another sorting algorithm, often insertion sort. It is mainly useful when input is uniformly distributed over a range.

Algorithm:

The algorithm for bucket sort is as follows:

• Create a list of empty buckets (array).
• Iterate through the input array, putting each element in the correct bucket based on its value.
• Sort each bucket (using a different sorting technique like insertion sort or quick sort).
• To get the sorted array, concatenate the sorted buckets.

Time Complexity:

• Worst case: O(n^2)
• Best case: Ω(n+k)
• Average case: Θ(n+k)

where n is the number of elements and k is the number of buckets.

Implementation of the algorithm in Java:

import java.util.*;

public class BucketSort {
    public static void bucketSort(int[] arr, int bucketSize) {
        if (arr.length == 0) {
            return;
        }

        // Find minimum and maximum values in the array
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < minValue) {
                minValue = arr[i];
            } else if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }

        // Create buckets and distribute elements into them
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (arr[i] - minValue) / bucketSize;
            buckets.get(bucketIndex).add(arr[i]);
        }

        // Sort buckets and concatenate them into a single array
        int currentIndex = 0;
        for (int i = 0; i < bucketCount; i++) {
            List<Integer> bucket = buckets.get(i);
            Collections.sort(bucket);
            for (int j = 0; j < bucket.size(); j++) {
                arr[currentIndex++] = bucket.get(j);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        int bucketSize = 10;
        bucketSort(arr, bucketSize);
        System.out.println(Arrays.toString(arr));
    }
}

The algorithm works by first determining the array’s minimum and maximum values, then forming buckets and distributing the array’s items into them depending on their values. The buckets are then separately sorted before being concatenated into a single sorted array.

Problems based on Bucket sort:

• Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Solution:

1. Create a countMap to count the frequency of each word in the words array.
2. Create a list of bucket to store the words with the same frequency. Each bucket at index i will store the words with frequency i.
3. Iterate through the countMap and add each word to the corresponding bucket based on its frequency.
4. Iterate through the bucket list in reverse order (from the highest frequency to the lowest) and add the first k words from each non-empty bucket to the result list. If there are ties in frequency, sort the words lexicographically before adding them to the result list.
5. Return the result list.

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> countMap = new HashMap<>();
        for (String word : words) {
            countMap.put(word, countMap.getOrDefault(word, 0) + 1);
        }

        // Create a list of buckets to store the words with the same frequency
        List<String>[] bucket = new List[words.length + 1];
        for (String word : countMap.keySet()) {
            int count = countMap.get(word);
            if (bucket[count] == null) {
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(word);
        }

        // Create a list to store the k most frequent words
        List<String> result = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
                result.addAll(bucket[i].subList(0, Math.min(k - result.size(), bucket[i].size())));
            }
        }
        return result;
    }
}

• Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.

Example:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Solution:

class Solution {
    public String frequencySort(String s) {
    
   if (s == null || s.length() == 0) {
            return "";
        }
        
        Map<Character, Integer> frequencyMap = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        List<Character>[] bucket = new List[s.length() + 1];
        
        for (char key : frequencyMap.keySet()) {
            int frequency = frequencyMap.get(key);
            
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            
            bucket[frequency].add(key);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i]) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        
        return sb.toString();
    
}

}

here,

1. We begin by constructing afrequencyMap to hold the frequency of each letter in the provided text.
2. The characters are then stored in buckets based on their frequency in a bucket.
3. We iterate through frequencyMap adding each character to the bucket that corresponds to its frequency.
4. Then, in reverse order, we iterate through the bucket array appending each character to the result string sb based on its frequency.
5. Then return the result string sb.

Note: also read about Radix Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py