computer algorithms for statistical calculations

Knowing the distribution well, the hash function may prove to be a perfect hash function, or close to perfect for many input vectors. Knowing the data source distribution, one can build a good hash function.

The authors claim this algorithm has better performance (up to 30% better) than the popular Quick-Sort Algorithm.

Of course, your algorithm would be computationally faster than the the Histogram Sort algorithm because there would probably not be a need to do the first pass (described in the link) since you already know the distribution.Įdit: given your new criteria of your question, (though my previous answer concerning Histogram Sort links to the respectable NIST and contains performance information), here is a peer review journal article from the International Conference on Parallel Processing:Īdaptive Data Partition for Sorting Using Probability Distribution You could add some extra logic to it so that you calculated the size and/or positions of the various buckets based upon properties of the distribution (ex: for Gaussian, you might have a bucket every (sigma/k) away from the mean, where sigma is the standard deviation of the distribution).īy having a known distribution and modifying the standard Bucket Sort algorithm in this way, you would probably get the Histogram Sort algorithm or something close to it. If the data you are sorting has a known distribution, I would use a Bucket Sort algorithm. However any additional information is welcome. Something like 'in the case of gaussian distributed data, XYZ algorithm is the fastest on average, as was proved by Smith et al. I'm adding a bounty to this question, because I'm looking for definite answers with sources, not speculation. Isn't this a very common case (the Gaussian case, for example)? I'm pretty surprised the answer isn't a wiki link to a thourough page discussing this issue. This would give you an estimate of the final position of each number, which you could use to place them close to their final position.

So my question is, are there any sorting algorithms that take into account that kind of information? How good are they?Īn example to clarify: if you know the distribution of your data to be Gaussian, you could estimate mean and average on the fly as you process the data. It just occurred to me, if you know something about the distribution (in the statistical sense) of the data to sort, the performance of a sorting algorithm might benefit if you take that information into account.

Computer algorithms for statistical calculations