Front page | perl.perl5.porters |
Postings from July 2004
david nicol asked for comments thus: > On Tue, 2004-06-29 at 18:24, Glenn Linderman wrote: > > > I'm not sure offhand how many result elements are at the crossover > > between where bubble sort is best and heapsort becomes best, but I > > believe both of those will generate entries in sorted order faster than > > sorting the whole array to throw away most of the results. > > That is what I was trying to figure out, and I would like peer review > on my result of bubble for five or less and heap for six or more. M=5 > is the judgement call, giving always two (after the unavoidable initial > comparison) in insertion mode whereas bubble gives an expected two with > random data. I meant to reply to the porters at large earlier, but succeeded in only contacting a couple people. Heap sort is going to double the number of comparisons realtive to a binary search, since it has to do two compares at each level of the log M tree. It saves moves, but moves are cheap, and comparisons are dear, so I don't see heap sort ever being the winner. You can get N log M comparisons from the binary search you have at http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html and N * M moves, which will beat the wholesale sorts for small enough M. But the wholesale merge sort does a nice job on orderly data, and will beat the specialized sort if there are fewer than log M runs, for example. I can imagine keeping track of where insertions happen, and biasing the initial guess-point for the binary search when it appears the data are non-random. That could make comparisons look more like N than like N log M for orderly data. -- jplThread Previous | Thread Next