0

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.

1
2

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

3
  • @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
0

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;
}

count is your answer.

0

Insertion sort will pick an element (iterated the process from 2nd element to last element), shifts all elements which are greater than the picked up element in the left part of the array by one position to the right and inserts it at correct position.

  • Count swaps while performing Insertion sort

    void insertionSort(int *array, int size) {

       int key, j,swap=0;;
    
       for(int i = 1; i<size; i++) 
      {
    
          key = array[i];//take value
    
          j = i;
    
          while(j > 0 && array[j-1]>key) {
    
             array[j] = array[j-1];
             swap++;
             j--;
          }
          array[j] = key;   //insert in right place
       }
    }
    
  • Finding bigger elements

Look at the insertion sorting algorithm closely and can you figure out when exactly an element swap is happening? The elements are swapped whenever a bigger element is found on left side of sorted array while trying to insert picked up element in correct position. So we can use this technique and count the number of swaps required without moving the elements in the array.

int  getBiggerElementsCount(int *array, int size) {
  //base case
  if (size <= 1) {
    return 0;
  }
  int biggerElements = 0;
  //starting at 2nd element as first element is already sorted
  //and no swaps are required.
  for (int i = 1; i < size; i++) {
    //find number of elements less than current
    int moveMe = ar[i];
    for (int j = i - 1; j >= 0; j--) {
      if (moveMe < ar[j]) {
        //found small element on my (ar[i]) left
        ++biggerElements;
      }
    }
  }
  return biggerElements;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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