Javalobby - Comments for "Fast O(n) Integer Sorting Algorithm"
http://java.dzone.com/articles/fast-integer-sorting-algorithm
Comments for "Fast O(n) Integer Sorting Algorithm"enyes, but more generally you
http://java.dzone.com/articles/fast-integer-sorting-algorithm#comment-26595
<!--paging_filter--><p>yes, but more generally you can say, it is because of the range the integer values has to be (max and min value). An analogous sort can be even applied to (uniformly distributed) decimal values within the range [0,1) -> bucket sort.</p><p>and: the sorting isn't based on comparison. A comparison based sort always requires Omega(n log n) in the worst case.</p><p>See the wikipedia entries of <a href="http://en.wikipedia.org/wiki/Radix_sort">radix sort</a> and <a href="http://en.wikipedia.org/wiki/Counting_sort">counting sort</a> for more information (or the book "introduction to algorithms" from thomas cormen)</p>Wed, 03 Mar 2010 03:20:55 -0500peathalcomment 26595 at http://java.dzone.comInteresting..When you study
http://java.dzone.com/articles/fast-integer-sorting-algorithm#comment-26587
<!--paging_filter--><p>Interesting..</p><p>When you study computer science in the university you actually prove that there is no sorting algorithm that runs with less than nlog(n) time... i don't remember the exact proof..</p><p> I need to deepen in this to understand how this is possible. Is it because of the prerequsite that the array is positive integer array? </p>Wed, 03 Mar 2010 02:38:55 -0500alonazcomment 26587 at http://java.dzone.comHere is a Java - OpenCL demo
http://java.dzone.com/articles/fast-integer-sorting-algorithm#comment-26571
<!--paging_filter--><p>Here is a Java - OpenCL demo using the GPU for sorting I added two days ago to the demo repository:</p><p>http://github.com/mbien/jocl-demos/tree/master/src/com/mbien/opencl/demos/radixsort/</p><p>it overtakes dual pivot quicksort (jdk7) at 32k elements and is already more than 13 times faster with 8Mil. elements. (Heap2GPU and GPU2Heap data transfer included - no cheating).</p><p>(bitonic sort is in the repro too) </p><p>If you have sorting as bottleneck - its somethimes worth to think out of the box ;) </p>Tue, 02 Mar 2010 13:50:57 -0500mbiencomment 26571 at http://java.dzone.comThese O(n) algorithms are
http://java.dzone.com/articles/fast-integer-sorting-algorithm#comment-26567
<!--paging_filter--><p>These O(n) algorithms are generally in O(n + (or *) k) where k is another aspect that you are leveraging to accelerate the sort. The speed up is due to the fact that you are not comparing elements, but rather that you are treating them as ordinal. In counting sort, you are preallocating memory for every possible value. This means that the algorithm cannot scale as the memory requirement should be too large. Bucket-sort, on the other hand, allows O(kn) sorting where you apply k O(n) sorts, but requires less memory.</p><p>> Now I wondered: is this necessary in real applications? E.g. somewhere in Java? </p><p>If your application has lots of calculations requiring sorting (e.g. scientific applications), and if this is a bottleneck, then of course, it is useful. You might even combine different sorting algorithms if you want to achieve peak performance. If, on the other hand, you only program DB-bound (fetch the data and present the data) applications, then no it is not useful since the DB has optimised sorting algorithms (and a order lower constant value). Rule of thumb: use a standard comparison-based sorting algorithm if n is small and doesn't affect performance.</p>Tue, 02 Mar 2010 11:18:33 -0500sv102431comment 26567 at http://java.dzone.comIt's called a histogram sort.
http://java.dzone.com/articles/fast-integer-sorting-algorithm#comment-26561
<!--paging_filter-->It's called a histogram sort.Tue, 02 Mar 2010 10:52:39 -0500bl92550comment 26561 at http://java.dzone.com