[Development] Radix sort

[Luís Gabriel Lima]

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
<rafael.lobo at openbossa.org>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 <markg85 at gmail.com> 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
>> Development at qt-project.org
>> http://lists.qt-project.org/mailman/listinfo/development
>>
>
>
>
> --
> Rafael Brandao @ INdT
>
> _______________________________________________
> Development mailing list
> Development at qt-project.org
> http://lists.qt-project.org/mailman/listinfo/development
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20120711/59d45999/attachment.html>