You cannot solve all the possible cases of string sorting using Radix Sort in O(N). More info here: http://htmltolatex.sourceforge.net/samples/sample4.html
Best Regards, -- Luís Gabriel OpenBossa - INdT On Tue, Jul 10, 2012 at 9:01 PM, Rafael Brandao <[email protected]>wrote: > 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 > >
_______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
