Efficient way to count number of swaps to insertion sort an array of integers in increasing order

Question

Given an array of values of length n, is there a way to count the number of swaps that would be performed by insertion sort to sort that array in time better than O(n²)?

For example :

arr[]={2 ,1, 3, 1, 2};  // Answer is 4.

Algorithm:

for i <- 2 to N

    j <- i

 while j > 1 and a[j] < a[j - 1]

       swap a[j] and a[j - 1]  //I want to count this   swaps?

       j <- j - 1

Answer 1

If you want to count the number of swaps needed in insertion sort, then you want to find the following number: for each element, how many previous elements inn the array are smaller than it? The sum of these values is then the total number of swaps performed.

To find the number, you can use an order statistic tree, a balanced binary search tree that can efficiently tell you how many elements in the tree are smaller then some given element. Specifically, an orde statistic tree supports O(log n) insertion, deletion, lookup, and count of how many elements in the tree are less than some value. You can then count how many swaps will be performed as follows:

1. Initialize a new, empty order statistic tree.
2. Set count = 0
3. For each array element, in order:
   1. Add the element to the order statistic tree.
   2. Add to count the number of elements in the tree less than the value added.
4. Return count,

This does O(n) iterations of a loop that takes O(log n) time, so the total work done is O(n log n), which is faster than the brute-force approach.

---

If you want to count the number of swaps in selection sort, then you can use the fact that insertion sort will only perform a swap on the kth pass if, after processing the first k-1 elements of the list, the element in position k is not the kth smallest element. If you can do this efficiently, then we have the following basic sketch of an algorithm:

1. Set total = 0
2. For k = 1 to n:
   1. If the element at index k isn't the kth largest element:
      1. Swap it with the kth largest element.
      2. Increment total
3. Return total

So how do we implement this efficiently? We need to efficiently be able to check whether the element at a given index is the correct element, and also need to efficiently find the position of the element that really does belong at a given index otherwise. To do this, begin by creating a balanced binary search tree that maps each element to its position in the original array. This takes time O(n log n). Now that you have the balanced tree, we can augment the structure by assigning to each element in the tree the position in the sorted sequence that this element belongs. One way to do this is with an order statistic tree, and another would be to iterate over the tree with an inorder traversal, annotating each value in the tree with its position.

Using this structure, we can check in O(log n) time whether or not an element is in the right position by looking the element up in the tree (time O(log n)), then looking at the position in the sorted sequence at which it should be and at which position it's currently located (remember that we set this up when creating the tree). If it disagrees with our expected position, then it's in the wrong place, and otherwise it's in the right place. Also, we can efficiently simulate a swap of two elements by looking up those two elements in the tree (O(log n) time total) and then swapping their positions in O(1).

As a result, we can implement the above algorithm in time O(n log n) - O(n log n) time to build the tree, then n iterations of doing O(log n) work to determine whether or not to swap.

Hope this helps!

Answer 2

The number of interchanges of consecutive elements necessary to arrange them in their natural order is equal to the number of inversions in the given permutation.

So the solution to this problem is to find the number of inversions in the given array of numbers.

This can be solved in O(n log n) using merge sort.

In the merge step, if you copy an element from the right array, increment a global counter (that counts inversions) by the number of items remaining in the left array. This is done because the element from the right array that just got copied is involved in an inversion with all the elements in present in the left array.