Algorithm-Sort an array with a minimum amount of swapping two consecutive elements

The number of inversions of a permutation relative to another permutation is the minimum number of adjacent swaps required to transform one into the other. A little bit of abstract algebra shows that we're interested in finding the rotation of the input array that minimizes the number of inversions relative to sorted order.

There are several algorithms for counting inversions. The one that's useful here uses a binary-indexed tree to make the following pseudocode run quickly (O(n log n)).

Let P[1], ..., P[n] be the input permutation on 1, ..., n
For k = 1, ..., n
    Initialize A[k] = 0
End For
For j = 1, ..., n
    I[P[j]] = A[j]    # Number of elements before and greater than P[j]
    For k = 1, ..., P[j] - 1    # Replace this loop with an O(log n) tree operation
        A[k] = A[k] + 1
    End For
End For
The total number of inversions is I[1] + ... + I[n]

Now, if we rotate one element j from the end of the array to the beginning, we update

For k = 1, ..., j - 1    # Replace this loop with an O(log n) tree operation
    I[k] = I[k] + 1
End For
I[j] = 0

and recompute the sum in constant time accordingly. Repeat the appropriate number of times and take the minimum.

According to the Wikipedia article on comparison-based sorting, an asymptotic worst-case complexity of O(n log n) is optimal, which would make an algorithm even without the constraints of swapping only adjacent elements impossible. To see that a bound of O(log n) is impossible under the given constraints, consider the class of instances

n,n-1,n-2,...,1

for any nonnegative integer n, i.e. the lists which are sorted in exactly the wrong way. At least n-1 swaps are necessary to move the 1 to the first position, which cannot be done int O(log n) time. Furthermore, even a list which is sorted in the desired order has to be read to decide that it is, which also needs at least n-1 comparisons, rendering a worst-case bound of O(log n) impossible.

With a binary indexed tree (aka Fenwik tree), we can add elements and calculate their prefix sums in O(log n) time. One way to solve your problem using it is the following:

(1) Calculate the permutation's inversion vector: traverse the array and for each index i and element v, first add (i - prefix sum 0 to v) to the results, then add 1 at index v in the tree. If you think about it, i equals the number of inversions we would count for i if all preceding elements were greater than i; so we subtract the number of elements less than v encountered so far, which is exactly the prefix sum up to index v in the tree so far. This operation takes time O(n * log n) For example,

Array:           {1,5,4,6,2,0,3}

Traversal:      (0-0)
                  (1-1)
                    (2-1)
                      ...

Inversion vector: 0 0 1 0 3 5 3

(2) Now the fun part. Since we are allowed to rotate the sorted order, let's think what would happen if we moved the 6 in the target-sorted-order to the beginning: instead of zero, the 6 in our array would now count 3 inversions, a number equal to the count of elements preceding it; and each element following the 6 will have one inversion less since it would no longer need to be swapped with 6. Continue:

Array:                {1,5,4,6,2,0,3}
Original vector:       0 0 1 0 3 5 3  (12)
V with 6 at start:     0,0,1,3,2,4,2  (12)
V with 5,6 at start:   0,1,0,2,1,3,1  (8)
V with 4,5,6 at start: 0,1,2,1,0,2,0  (6)
(3,4,5,6,0,1,2)        0,1,2,1,0,2,6  (12)
(2,3,4,5,6,0,1)        0,1,2,1,4,1,5  (14)
(1,2,3,4,5,6,0)        0,0,1,0,3,0,4  (8)

But this operation can take time O(n) if we simply use the elements' position in the array, which we can hash beforehand. Given original inversion vector 0 0 1 0 3 5 3, we repeatedly apply the following operation to its sum of 12 and choose the minimum:

12 
 + 3 - 3 (=12) // + index of 6 - (n - index of 6 - 1)
 + 1 - 5 (=8)  // + index of 5 - (n - index of 5 - 1)
 + 2 - 4 (=6)  // ...
 + 6 - 0 (=12)
 + 4 - 2 (=14)
 + 0 - 6 (=8)

As we can see, the minimum swaps needed are 6 if we choose rotated target order (4,5,6,0,1,2,3):

Array:    {1,5,4,6,2,0,3}
Target:   {4,5,6,0,1,2,3}
# Swaps:   0 1 2 1 0 2 0

Swaps:             0,2
           5,1
             4,1
           4,5
               6,1
                 0,1