Counting Inversions

Merge Sort: Counting Inversions

Concept:

 Count Inversions in an array

Implementation:

	/// O(NlogN)
	#include<bits/stdc++.h>
	using namespace std;
	#define LL long long
	int n;
	void print(int ar[])
	{
	for(int i = 0; i < n; i++)
	{
	cout << ar[i] << " ";
	}
	cout << endl;
	}
	long long ans = 0;
	void merge(int a[], int i, int j)
	{
	int mid = ((i+j)/2) + 1, X = j + 1;
	int s = i;
	int *arr = new int [j - i + 1];
	j = mid;
	int k = 0;
	while(i < mid && j < X)
	{
	if(a[i] <= a[j])
	{
	arr[k] = a[i];
	i++;
	}
	else
	{
	arr[k] = a[j];
	ans += (mid - i);
	j++;
	}
	k++;
	}
	for(; i < mid; i++,k++) arr[k] = a[i];
	for(; j < X; j++, k++) arr[k] = a[j];
	for(k = 0; s < X; s++, k++)a[s] = arr[k];
	delete [] arr;
	}
	void merge_sort(int a[], int i, int j)
	{
	if(i < j)
	{
	int mid = (i + j)/2;
	merge_sort(a,i,mid);
	merge_sort(a,mid+1, j);
	merge(a,i,j);
	}
	}
	int main()
	{
	// freopen("in.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while(T--)
	{
	ans = 0;
	scanf("%d", &n);
	int *ar = new int [n];
	for(int i = 0; i < n; i++)
	{
	scanf("%d", &ar[i]);
	}
	merge_sort(ar,0,n-1);
	cout << ans << endl;
	// print(ar);
	}
	return 0;
	}

view raw InversionCount.cpp hosted with ❤ by GitHub

Share: