# efficient way to count number of swaps in insertion sort

I am browsing some online coding challenge online and got struck somewhere . Objective of program is to find maximum number of swaps required in sorting an array via insertion sort in efficient time

the first approach that is brute force approach gives the O(n^2) complexity

The next i can think of is merge sort algorithm the code i use for that is

``````#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int mergesort(int *,int);
int _mergesort(int *,int *,int,int);
int merge(int *,int *,int,int,int);

int mergesort(int arr[],int n)
{
int temp[n];
return _mergesort(arr,temp,0,n-1);
}

int _mergesort(int arr[],int temp[],int left,int right)
{
int mid,count=0;
if(right>left)
{
mid=(left+right)/2;
count=_mergesort(arr,temp,left,mid);
count+=_mergesort(arr,temp,mid+1,right);
count+=merge(arr,temp,left,mid+1,right);
}
return count;
}

int merge(int arr[],int temp[],int left,int mid,int right)
{
int i, j, k;
int count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
count = count + (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i];

return count;
}

int main()
{
int n,tc,i;
cin>>tc;
while(tc)
{
cin>>n;
int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
cout<<mergesort(arr,n);
tc--;
}
return 0;
}

The example test case is
Sample Input:
2
5
1 1 1 2 2
5
2 1 3 1 2

Sample Output:
0
4
``````

this gives me a complexity of nlogn Initially the program reads number of test case that is 2 and followed by two test case

the algorithm works fine for small range of values but show time limit exceeded error in some test case .

What is the most efficient way of doing this i cant find out any suggestion or edits would be appreciated.

-

The key to this problem isn't to try to find the worst case situation, but rather find the pattern to be able to create the function `sorts(x) = maximum number of sorts for an array of length x`.

The insertion sort is one of the 'easy' forms of a sorting network. A sorting network for an insertion sort looks like:

Each line is a comparison and possible swap. Compare the second and first spot. Possibly swap. Then compare third and second, and then second and first. etc...

As an aside, this is what a bubble sort looks like in a sorting network.

And if you can do parallel comparisons (the whole point of the sorting network)... they both look like:

Looking at just the lines, this is a triangle...

``````2: .
3: ..
4: ...
5: ....
``````
• For an array of size 2, you need one comparison.
• For an array of size 3, you need to sort an array of size 2, and do two more comparisons.
• For an array of size 4, you need to sort an array of size 3, and do 3 more comparisons.
• For an array of size X, you need to sort an array of size x-1 and do x-1 more comparisons.

The sequence is: 1, 3, 6, 10, ...

This is a well known sequence - `(n * (n+1))/2`

Remembering that this starts from 2 rather than 1...

`sorts(x) = ((x - 1) * x)/2`

-
@Michale 1 1 1 2 2 what about this array where you don't need any comparision. I still don't get the exact approach for this i appreciate your help but please could you make it more clear to me so that i can design a algorithm – prateeak ojha Oct 2 '13 at 20:29
And basically i need to calculate the number of shifts required rather than the number of comparisions – prateeak ojha Oct 2 '13 at 20:31
I'll have to think about this some more, though admittedly, it is a difficult problem (or it wouldn't be part of the challenge). – user40980 Oct 2 '13 at 20:56
thanks hope you ll come up with a solution :) thanks – prateeak ojha Oct 2 '13 at 21:48

You can make a order statistic tree from red black tree and not binary tree because that will fail in case of insertion of keys of sorted fashion.

Then you can implement `Rank(T,x)` to find the node x position in the current tree. This will be one indexed rank.

So no of elements greater than this will be `N-Rank(T,x)` where `N` is total no of nodes. This is the no it has to shift right by.

so

``````swaps=0;
for all keys in array{
insert in Order statistic Tree;
g=current one based index-Rank(key);
count+=g;
}
``````