Saturday 15 March 2008

Bubblesort with N processors cannot still be reduced from O(n)

So, continuing with the previous post, let's assume we can make N comparisons simultaneously. Bubblesort won't still improve the speed from O(n); in the pathological case, where we have MAX, x, x2, x3, ..., x(N-1). Only one comparison per cycle will return that a swap has to be executed. so, we still have to do N-1 swaps.
Now, how we use all this comparisons? Well, a simple algorithm will be to make N/2 comparisons per cycle, comparing all elements xE with xE+1 (where E is all the even numbers). In the next cycle, we compare xE-1 with xE. Why not do both at the same time? It is very simple: we might have a problem that both return true, and we must execute both swaps; which is the equivalent of swapping xE-1 with xE+1. But how do we know that? We must compare the results of the comparisons, and we still have the problem of how xE+2 may compare with xE+1.

Add to Technorati Favorites

1 comment:

Gonzalo Merayo said...

I'm pretty sure no sort can be reduced from O(n). hmmm...I'll try to prove it.