Re:JavaScript Visualization of Sorting Algorithms
by foob on Thursday March 10, 2011 @09:29PM
(#2311888)
This isn't exactly what you're talking about but I think that it might interest you: Adaptive Data Partitioning Using Probability Distribution by Xipeng Shen, Yutao Zhong, and Chen Ding (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.31...). They estimate the probability distribution using a subset of the data and then use this to determine the partitions.
Re:JavaScript Visualization of Sorting Algorithms
by anonymoushn on Friday March 11, 2011 @03:19AM
(#2312637)
This seems like a more developed version of what Perceval had mentioned. Using German Tank Problem-based estimates would involve assuming a uniform distribution from the beginning.
Re:JavaScript Visualization of Sorting Algorithms
by T-hawk on Friday March 11, 2011 @12:28PM
(#2314084)
I'm not aware of any general-purpose package for German Tank Sort, but it is sometimes implemented in specialized applications where you know a distribution is close to uniform. Run one round of estimating, then run bubble sort. The worst-case time of course is N², but if your estimator is sufficiently good and data is sufficiently uniform, you could possibly achieve an average time of fewer than log N passes through bubble sort so break the N log N barrier for your typical case.
You wouldn't have to know the upper or lower bounds of the list, you could estimate them progressively from a smaller sample. Then you could insert each item to position N based on your distribution estimate. The further you get through the list, the better the distribution estimate would get, and inserting would get more accurate.
Is this plausible? Has this been done already?