Re: [boost] [sorting]

From: Herve Bronnimann (hervebronnimann_at_[hidden])
Date: 2007-03-18 17:56:52

Sam: again I'm curious (read: highly skeptical).  When you say "much slower" do you base yourself on actual data? I.e. Have you tried it? The reason I ask is that I don't believe it. Let's talk for concreteness of three levels (name, number, grade).  Any algorithm that does three passes on the data when one will do will be slower (doesn't matter how complicated your comparison is, if all the name data is distinct the outer sort comparison will conclude quickly).  Radix sort insists on doing all three passes even if all names are distinct.  I'm sure data will back me up, if not please show me the numbers.  --Herve
--
Hervé

Sent from my BlackBerry® wireless handheld  
Please excuse misspellings and typos  

-----Original Message-----
From: Sam Schetterer <samthecppman_at_[hidden]>
Date: Sun, 18 Mar 2007 08:04:31 
To:boost <boost_at_[hidden]>
Subject: Re: [boost] [sorting]

On March 18, Henrik Sundberg wrote
>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.
Yes, that can be done, but it is much slower because of the many operations
that need to be done. In addition, since radixquicksort is to be used for
strings, the compare operation will still have to use a string comparison,
severly slowing it down. Also, if you use a function that creates a string,
you can do an extrordanarily complex sort, like sort by name, then number,
then grade, and if grade is below a B+, then sort by age. This can be done
because you cn change how the id string is created. That is why quicksort is
useful.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost