Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

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

share|improve this answer
    
@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). –  MichaelT Oct 2 '13 at 20:56
    
thanks hope you ll come up with a solution :) thanks –  prateeak ojha Oct 2 '13 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.