0
$\begingroup$

I know this post. But I still have no idea to adapt the bucket sort algorithm to handle input with a gaussian / normal distribution. Can someone provide me a Pseudocode / Python code for that? So far I tried the following, but sadly it does not work, and I don't understand why.

def bucket_sort(numbers):
    mean = sum(numbers) / len(numbers)
    variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
    std_deviation = math.sqrt(variance)

    num_buckets = int( math.sqrt(len(numbers)) )
    buckets = [[] for _ in range(num_buckets)]

    for num in numbers:
        index = int( ( (num - mean) / std_deviation) * num_buckets)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_numbers = [num for bucket in buckets for num in bucket]

    return sorted_numbers
$\endgroup$

2 Answers 2

1
$\begingroup$

Let $F$ denote the cumulative distribution function for your distribution. Suppose you want $N$ buckets. Then use the following buckets:

$$(F^{-1}(0),F^{-1}(1/N)],(F^{-1}(1/N),F^{-1}(2/N)],\dots,(F^{-1}((N-1)/N),F^{-1}(1)].$$

This ensures that about $1/N$ of the samples fall into each bucket. Then, use bucket sort with these buckets.

To compute which bucket a value $x$ falls into, it suffices to compute the cdf for $x$. In particular, $x$ goes into bin number $\lfloor F(x) N \rfloor$.

This works for any distribution, assuming the distribution is known and you can compute the cdf.

$\endgroup$
3
  • $\begingroup$ I really try to understand that, but I don't. First I have no idea how to compute/approximate that. Second: If I only compute the boundaries of the buckets, and not the indices, I have to loop over the element to find the correct bucket. I could improve this using binary search, but I still mess up the time complexity of bucket sort... Can you help me further, maybe provide a codeline for calculating the index, assuming the buckets have an index 0,1,...,b? $\endgroup$
    – Titanlord
    May 23, 2023 at 17:30
  • $\begingroup$ The inverse $\text{cdf}$ gives the bounds of the intervals. But to get the bucket where a given value goes, you need the direct $\text{cdf}$. $\endgroup$
    – user16034
    May 24, 2023 at 6:40
  • $\begingroup$ @YvesDaoust, oh, right! Thank you. Answer edited accordingly. $\endgroup$
    – D.W.
    May 24, 2023 at 15:42
1
$\begingroup$

So I finally understand, what is happening. The input is distributed with a normal distribution. This leads us to a normal probability distribution function PDF for the probability of the elements. We can describe the distribution using the mean µ and derivative $\sigma$:

$$ µ = \frac{\sum_{n \in N} n}{| N |} \quad \sigma = \sqrt{\frac{ \sum_{n \in N} (n - µ )^2 }{| N |}} $$

The cumulative distribution function CDF is the integral over the PDF and creates a uniform random distributed output for the elements in the initial distribution. The reason for the uniformity is based on a phenomena called probability integral transform. In the case of normal distribution the CDF is closely related to the errorfunction, BUT NOT exactly the error function. A mistake that took me way too long to realise. The CDF is as follows:

$$ f(x) = \frac{1}{2} * (1 + erf(\frac{x - µ}{\sigma \sqrt 2})) $$

where $erf$ refers to the error function. Last but not least we want buckets and because we have an integral over probability, we only have values between 0 and 1. We can simply rescale using the number of buckets and we are done. This way, we can build a bucket sort for normal/gaussian distribution which is still in $O(n)$. My result:

import math
import scipy.stats

def bucket_sort(numbers, mean, deviation):
    # Just recompute here to see what happens
    mean = sum(numbers) / len(numbers)
    variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
    deviation = math.sqrt(variance)

    num_buckets = int( math.sqrt(len(numbers)) ) 
    buckets = [[] for _ in range(num_buckets)]

    for num in numbers:
        # index = scipy.stats.norm.cdf(num, mean, deviation)
        tmp = (num - mean)/(deviation*math.sqrt(2))
        index = 0.5 *(1+math.erf(tmp))
        index = int(index * num_buckets)

        # Append rescaled value to bucket
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_numbers = [num for bucket in buckets for num in bucket]

    return sorted_numbers

# example call
mean = 50
std = 20
input = scipy.stats.norm.rvs(50,20,100)
input = [int(i) for i in input]
print(bucket_sort(input,mean, std))

I am not quite sure whether I should thank Yves Daoust or not :D At least he tried to help me, which I appreciate a lot, but I am sorry, your input wasn't quite helpful. What helped me a lot, was this post.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.