Hello Mark, Radix sort cannot be used for all sorting cases, like the string sort you've been looking for. It can only be used when you know the range of the numbers that will be sorted.
Let's say you know that there will be only numbers between 0 and 1000000 on a given array/list. Then you can go through each element on this array in O(N) and count how many times each number shows up on this list. Afterwards, you'll only need to go through the list of number occurrences in O(M), M being the size of range of numbers. When you go through this secondary list, you'll already have the numbers sorted and then you can place them on your resulting array on their correct positions very fast. Radix sort is what you would probably do when you're manually sorting things, like cards. :-) Regards, On Tue, Jul 10, 2012 at 5:20 PM, Mark <[email protected]> wrote: > Hi Devs, > > Not anything Qt related but something i thought might be interesting > for you guys to know. > Some keywords that probably spark interest: "in place sorting", "beats > quicksort and std::sort easily", "complexity: O(kN) for worst and best > performance" > > Here are a bunch of links for those interested. > http://attractivechaos.wordpress.com/2012/06/10/an-update-on-radix-sort/ > https://github.com/gorset/radix > > http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/221600153 > http://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html > > All the test cases I've seen talk about sorting integers and it seems > to shine there better then any other sorting algorithm existing. I > haven't found any Radix sort benchmark yet for string sorting. > > Cheers, > Mark > _______________________________________________ > Development mailing list > [email protected] > http://lists.qt-project.org/mailman/listinfo/development > -- Rafael Brandao @ INdT
_______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
