sorting series of numbers by swaping adjacent numbers

Question

we have n numbers and we want to sort it. but in sorting we can just swap two adjacent numbers.( I mean if(A(i) > A(i+1) then we can swap A(i) with A(i+1) but not swaping A(i+3) with A(i) ). It is important to do it in O(nlogn). Any idea to how to do this?! :)

Answer 1

You have a restriction on swapping, but not on reading. So you could use something like a quicksort or a shellsort on a copy of the array first, to work out the final positions. Then you could write something that bubbles the values to their final position in the real array.

Answer 2

It is impossible to achieve O(nlogn) in worst case scenarios. Consider this array :

n (n-1) ... 2 1

You cannot sort this with less than n(n-1)/2 operations. Why? Let's make some useful definition. Call a pair of two array entries (A(i), A(j)) an inverse if i < j but A(i) > A(j). There are n(n-1)/2 inverses in the original array. How many inverses in the sorted array ? Answer : 0.

Each swap can only remove at most one inverse, therefore at least n(n-1)/2 swaps are needed.