Re: [boost] [sorting] Radix quicksort examples - sort within sort

From: Henrik Sundberg (storangen_at_[hidden])
Date: 2007-03-18 04:03:46

Isn't sort within sort handled by a more complex '<' operation?
I.e '<' returns the order of the inner sort, when the outer is equal.

/$

2007/3/18, Sam Schetterer <samthecppman_at_[hidden]>:
> Earlier, I loaded an example of how normal radix sort is useful. However,
> radixsort is almost impossible to use on data with varying lengths, making
> it unsiuted for strings. Luckily, the same "sort within sort" effect can
> still be achieved through radix quicksort. Although radix_quicksort is a
> string sort, it can be used for data of any type by using the
> create_id_string function, which is like sprintf, but instead of printing
> literal values for numbers (33 becomes "33"), the bytes are printed onto the
> string(33 becomes '!' (33 is the ascii value for '!')). Therefore, you get a
> fast sort that can accomplish what is called "sort within sort" k times
> faster than normal quicksort, where k is the number of bytes in the string.
> (normal quicksort is k(2 N log N), while radix quicksort is k + 2 N log N).
> Unfortunantly, it is not obvious how to implement radix quicksort, so I
> loaded an example of how to create an id string and use radix quicksort.
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>