5
$\begingroup$

Bucket sort algorithm lets you sort an array of $n$ elements in expected $O(n)$ time, supposing the elements are equally distributed in the $\lbrack 0,1 )$ interval.

Is there a way to modify the bucket sort in order to sort in expected $O(n)$ time an array of $n$ elements distributed in $\lbrack 0,1)$ according to the Gaussian distribution?

$\endgroup$
3
$\begingroup$

The algorithm works by choosing the number of buckets and the boundaries of the buckets such that in expectation the number of elements that land in a bucket is constant. The analysis is particularly simple for a uniform distribution, because uniformly sized buckets work.

For more complicated distributions you have to choose your bucket size more cleverly, but there is nothing stopping you from looking hard at the probability density function and creating more buckets in regions where you'd expect many elements to occur.

$\endgroup$
  • $\begingroup$ Specifically, use the inverse error function to find "optimal" bucket boundaries. Also remember that the key that you use for bucketing doesn't have to be the sort key, as long as the relationship is monotonic. $\endgroup$ – Pseudonym Sep 6 '17 at 8:06
  • $\begingroup$ First of all, thank you for your answer and comment. Bucket sort works well also because you can find in $O(1)$ the bucket in which your element a[i] will be stored: a[i] goes into bucket[ (1/n) * a[i] ]. Is the same possible with the inverse error function or any other function that defines our boundaries? $\endgroup$ – incud Sep 6 '17 at 8:15
  • $\begingroup$ @ignus It's not trivial but you can compute how much probability mass is left of the point to calculate the bucket number, e.g. if 1/3 of the probability mass is left of your point you want the 1/3*n-th bucket. It depends on the probability distribution how long calculating this takes. $\endgroup$ – adrianN Sep 6 '17 at 8:34
3
$\begingroup$

Mathematically this does exactly the same thing as @adrianN's answer, but it might be useful: you can transform random observations from the Gaussian distribution (or any other known distribution) to values uniformly distributed between 0 and 1, with a function which preserves order and which is invertible.

In the case of the Gaussian this is the function known as the error function, Z-score, etc. In general, it's the cumulative distribution function of a distribution.

So you can, for each element $x_i$, take the number $f(x_i)$. Sort these values. Then sort the $x_i$ by putting them in the same order (or apply $f^{-1}$ to get back the sorted original values).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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