[Development] Radix sort

[Rafael Brandao]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20120710/189a6d96/attachment.html>