[KLUG Programming] sorting, uniq'ing, and grepping

[Robert G. Brown]

On Mon, 14 Jul 2003 23:22:34 -0400, Erik Gillespie <rattles@yakko.cs.wmich.edu> wrote:

>> Not quite that simple. He still has to write the comparison code, which
>> is in essense a qsort callback.
>True, the callback can be tricky but in Tony's case....
No buts. You wrote the callback. Tony oughtta thank you. I did not assume that
was his compare, or missed it in the read-through. Doesn't matter, knowing
how to write the callback (parms and returns) is much of what's needed any-
way.

>> 0(n log n) performance is what you'll get if you're good. I was not
>> too worried about doing better, and it is possible to do a LOT worse! :)
>It is possible to do worse but if he sorts before searching for uniques 
>and stays away from insertion sort :P he should be fine.
I've written a lot of code where the sort is in integral part of looking for 
uniq values, so no need to flog that horse.

Possible to do worse? Heck, I've seen neophytes get 0(n**n) on single
routines, then do multiple passes through the data because they didn't
know how to roll it into one loop.

There are some clear upper limits to perfomances, but no lower limits to
human folly or ignorance.

							Regards,
							---> RGB <---