At 6/18/09 12:57 PM, GustTheASGuy wrote:
Interesting.
I finished the work I was doing on algorithm complexity classes. The first example I wrote was what I later found out to be Bubblesort. In worst case it does 1 + 2 + 3 ... + n comparisons for n elements in the list, best case n comparisons (obviously), and I didn't calculate average performance. It has a really bad progress rate though, as it belongs to polynomial running time n^2. Then I remembered what some guy told us about divide-and-conquer method in algorithms, so I started writing a better version. Doing bubblesort on two lists of n/2 elements and then merging them is much more efficient than doing bubblesort on n elements. (2(n/2)^2 + n < n^2 for n>1). So I use recursive programming to repeatedly divide the lists until I got pairs of 2 for optimal performance. Doing the division itself only takes ceil(log2(n)) steps, so it's nothing to worry about. It does use more memory than most algorithms though. Running time is n*log n. (less than n*ceil(log2(n))-2^ceil(log2(n)) operations)
Here's the code:
http://pastebin.com/m514cab2c
And listgenerator.py if you want to try it out on your PC:
http://pastebin.com/m16cd0576
I've been trying to find an algorithm that can sort lists of n items in n steps, but so far no success xD
I'll be in Israel until late August, so that's not possible. But we should definitely get something sorted out in the future, I have long dreamed to meet you and collaborate on a plan for world domination.
