4 ms·
This requires that you know the distribution before sorting; i'm not sure i ever do. I suppose you could pick the bounds by sampling: pick m random elements, s
by twic 7y ago
This requires that you know the distribution before sorting; i'm not sure i ever do.
I suppose you could pick the bounds by sampling: pick m random elements, sort them, and use those as the upper bounds. Better yet, pick km random elements, sort them, and use every k'th one as an upper bound. But the author's intention is that the number of classes is a (large!) fraction of the number of elements, so this would give you O(n log n) overall complexity, missing the point entirely.
I note that the classification algorithm, if run on already-sorted input, puts the classes in reverse order. If the classes are small, this doesn't matter, but if they were bigger, it would be worth using the TimSort trick of checking for runs of increasing elements and just flipping them.
I also note that this algorithm involves making three passes over the data: one to count the number of elements in each class, one to classify elements (this pass involves random access), and another to sort the classes. No worse than quicksort, but not ideal for an external sort, and maybe not too cache-friendly.
- thomasmg 7y agoRelated is samplesort https://de.wikipedia.org/wiki/Samplesort https://de.wikipedia.org/wiki/Samplesort - it is a comparison sort, and yes the complexity is also O(n log n), same as quicksort and merge sort. But it may have less branches, and possibly better cache locality. It is stable btw. Disadvantage: it uses a O(n) memory. I made some experiments with samplesort, and found with Java it can be about 40% faster than Arrays.sort, and for C++ maybe 5-10% faster: https://github.com/thomasmueller/fastSort_java https://github.com/thomasmueller/fastSort_java and https://github.com/thomasmueller/fastSort_cpp https://github.com/thomasmueller/fastSort_cpp
- twic 7y agoOh yes, i've basically reinvented samplesort! Fifty years too late, sadly.
- thomasmg 7y agoWell, the same thing happened to me. I implemented it, wrote a benchmark, and later was told this is samplesort... Historic footnote: samplesort was the Python sort algorithm before it was replaced with Timsort: https://bugs.python.org/issue587076 https://bugs.python.org/issue587076 (specially see the attached timsort.txt)
- wnoise 7y agoIn English: https://en.wikipedia.org/wiki/Samplesort https://en.wikipedia.org/wiki/Samplesort
- Sharlin 7y agoHm? Finding the exact bounds is a linear-time preprocessing step and as such doesn’t affect the complexity of the algorithm as a whole.
- twic 7y agoI don't think you can find k equally spaced class bounds in linear time.
- nabla9 7y agoYou can learn distribution by sampling or by going trough the dataset once.
- enriquto 7y agoAnd once you do through your dataset once, how do you store your distribution? By binning it into a histogram? This is precisely what bucket sort does. I guess there is a continuum of sorting algorithms between flashsort and bucket sort, according to the granularity of the binning.
- zodiac 7y agoIf you know the type of distribution but not the parameters,you can sometimes go through the data once and estimate the parameter (maybe exactly) without "storing the distribution" via histograms. Eg if you know the data is drawn from a uniform distribution U(a,b) but you don't know a or b.
- repsilat 7y agoMaybe this goes without saying, but for a fixed accuracy the number of samples required to estimate the distribution parameters does not depend on the number of samples available. Maybe if you need to sort more samples you need more accuracy, though.