12 Apr
2009
12 Apr
'09
7:28 p.m.
der Mouse wrote:
As far as I can tell, that would be exactly the right type of problem
for a theoretician. It's a pretty straight comparison of the
average-case and best-case big-O.
Peace... Sridhar
I've run
into "CS" graduates from the university who supposedly have
learned about really "good" sort algorithms (usually
"Shell-Metzner"), without understanding which situations an optimized
"bubble" is better for.
I'm not sure a CS graduate _should_. That's less an aspect of the
theoretical discipline CS is than of the correpsnoding practical
discipline (programming, software engineering, pick your favourite term
for it). Learning about the difference between shellsort's complexity
and bubblesort's and heapsort's is important. But I'm not sure I'd
expect a theoretician to correctly choose the right one for any
particular application.