Speed is always hard to test with sort routines because average speed depends on the distribution of the inputs. If your inputs are almost always nearly in order, then bubble sort performs quite well. If all permutations are equally likely, it definitely doesn't.
Most quick-sort variants improve speed for pathological cases. My feeling, though, is that unit tests are more useful for testing correctness. I have on occasion written "unit tests" for diagnostic purposes like speed tests. These tests don't have assertions based on speed, but instead produce diagnostic outputs. If you want to test speed, then a pretty easy way is to pick permutations at random, possibly emphasizing some kinds of permutations and run a sort for those permutations using both algorithms. Measuring speeds and taking the fastest iteration for each permutation should allow speed comparisons. The down side of this is that you wind up with a pretty slow test. If the speed difference isn't large, then the test won't even be very reliable. I think that the better option is to test off-line to verify the improvement and just make a note in the javadocs with the results. On Wed, Dec 23, 2009 at 10:27 AM, Benson Margulies <bimargul...@gmail.com>wrote: > On Wed, Dec 23, 2009 at 1:24 PM, Benson Margulies <bimargul...@gmail.com> > wrote: > > '4' was lame humor. Thanks for the concrete suggestion, I'll go there. > > To be clearer about the lame joke: it's easy to test 'does it sort'. > It's hard to test, 'does it correctly get implement this particular > variation on quickSort which can be distinguished from others only by > speed.' > > >
