snippetMinor
Bucket sort with gaussian distribution
Viewed 0 times
distributionwithbucketsortgaussian
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#80913, answer score: 4
Revisions (0)
No revisions yet.