On Jun 28, 2007, at 10:21 AM, Christopher Smith wrote:
On Jun 27, 2007, at 10:27 PM, Carl Lowenstein wrote:
Just for fun, try running each qsort implementation on an array that
is already sorted. This should bring out the worst-case performance.
So, I did try it out. I haven't had time to test out qsort1 with
it, but I expect it is similar to qsort3 which is bad enough (and
gives you an idea of just how qsort1 should be performing relative
to qsort3 if it really was O(n^2) ):
With 100,000 elements:
real 47m50.657s
user 40m1.524s
sys 0m43.578s
With 10,000 elements:
real 0m11.149s
user 0m9.891s
sys 0m0.162s
With 1,000 elements:
real 0m0.226s
user 0m0.162s
sys 0m0.017s
I didn't have the patience to try it with a million elements. ;-)
In case anyone still cares, I ran qsort1 with a presorted list today
as well. I had other tasks going on (sorry), so "real" time probably
should be ignored. Here are the numbers:
With 100,000 elements:
real 84m33.635s
user 57m4.105s
sys 0m54.458s
With 10,000 elements:
real 0m56.807s
user 0m21.191s
sys 0m0.351s
With 1,000 elements:
real 0m0.858s
user 0m0.162s
sys 0m0.017s
Looks a lot more like a quadratic curve to me.
--Chris
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
