Bucket Sort

Bucket Sort is a sorting algorithm.

It has below steps:

• Create buckets
• place all elements in each buckets according to certain rules
• sort the elements in one buckets using other sorting algorithms
• get sorted elements from buckets one by one

Let's see an example. Say we have an array [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]. We can create a array with length 10 as buckets. And then place elements into this bucket array.

[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

0
1    0.17, 0.12
2    0.26, 0.21, 0.23
3    0.39,
4
5
6    0.68
7    0.78, 0.72,
8
9    0.94,

bucket[n*arr[i]] = arr[i];

As you can see, after placing, the element is mostly ordered by the bucket number(or bucket array's index). So next we can use any other sorting algorithm to sort the elements in one bucket. And finally, we can get all ordered element from buckets one by one.

function bucketSort(nums: number[]): number[] {
    const n = 10;
    const bucket: number[][] = Array.from({ length: n }, (_) => []);
    for (let i = 0; i < nums.length; i++) {
        // nums[i] => [0, 1)
        // nums[i]*n => [0, 10)
        bucket[Math.trunc(nums[i] * n)].push(nums[i]);
    }
    const result: number[] = [];
    for (let i = 0; i < bucket.length; i++) {
        // use other sorting algorithm to sort the element in one bucket
        bucket[i].sort((a, b) => a - b);
        result.push(...bucket[i]);
    }
    return result;
}

const nums = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];
console.log(bucketSort(nums));

Sort Characters By Frequency

Now we know the basic process of bucket sort, let use this algorithm to solve this leetcode problem.

The problem is to sort the characters according to its frequency. Let take abbcccdd as an example.

First, we need to calculate its frequencies.

a: 1,
b: 2,
c: 3,
d: 2,

Next we create a buckets array. The array's index indicates the frequencies. So characters with the same frequencies should be in the same bucket. Note that the max frequency is the length of the source string, so the buckets array's length is the length of the source string and plus 1.

0
1    a
2    b, d
3    c
4

And finally, we can get elements from buckets. Because we need to most frequent element comes first. So we iterate the buckets array backward.

First, get 3 c, => [c, c, c]
Then, get 2 b, => [c, c, c, b, b]
Then, get 2 d, => [c, c, c, b, b, d, d]
Finally, get 1 a, => [c, c, c, b, b, d, d, a]

Ok, let see how to implement it in code.

function frequencySort(s: string): string {
    // get frequencies for all characters
    const frequency = [...s].reduce(
        (pre: Record<string, number>, cur: string) => {
            if (cur in pre) {
                pre[cur] += 1;
            } else {
                pre[cur] = 1;
            }
            return pre;
        },
        {}
    );

    // create buckets
    const buckets: string[][] = Array.from({ length: s.length + 1 }, (_) => []);

    // same frequecy characters should be in same bucket
    Object.entries(frequency).forEach(([key, value]) => {
        buckets[value].push(key);
    });

    const result: string[] = [];
    for (let i = buckets.length - 1; i > 0; i--) {
        for (let j = 0; j < buckets[i].length; j++) {
            for (let k = 0; k < i; k++) {
                result.push(buckets[i][j]);
            }
        }
    }

    return result.join("");
}