C++ – efficient way to count number of swaps in insertion sort

csorting

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.

Best Answer

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:

insertion sort
(source: wikimedia.org)

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.

bubble sort

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

sorting network

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

Related Topic