Count Inversions in an array | Set 1 (Using Merge Sort) - GeeksforGeeks

Count Inversions in an array | Set 1 (Using Merge Sort) - GeeksforGeeks: "include "





#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <fstream>

#include<vector>

#include<string>

using namespace std;

//#include<iostream>



unsigned int _mergeSort(int arr[], int tmp[], int beg, int end);

unsigned int merge(int arr[], int tmp[], int beg, int mid, int end);





unsigned int mergeSort(int arr[], int n){

    int *tmp= (int *) malloc (sizeof(int)*n);

    return _mergeSort(arr, tmp, 0,  n - 1);

}



unsigned int _mergeSort(int arr[], int tmp[], int beg, int end){

    int mid;

    unsigned int invCnt = 0;

//    if (end - beg  < 2) return 0;

    if(beg < end){

        mid = beg + (end - beg)/2;

        invCnt += _mergeSort(arr, tmp, beg,     mid);

        invCnt += _mergeSort(arr, tmp, mid + 1, end);

        invCnt += merge(arr,tmp,beg,mid + 1,end);

    }

    return invCnt;

}



unsigned int merge(int arr[], int tmp[], int beg, int mid, int end){

    unsigned int invCnt = 0;

    int i = beg;

    int j = mid;

    int k = beg;

    while(i <= mid-1 && j <= end){

        if( arr[i] < arr[j])

            tmp[k++] = arr[i++];

        else{

            tmp[k++] = arr[j++];

            invCnt += (mid-1) - i + 1;

        }

    }

   

    while(i <= mid-1)

        tmp[k++] = arr[i++];

    while(j <= end)

        tmp[k++] = arr[j++];

    for(int i = beg; i <= end; ++i)

        arr[i] = tmp[i];

    return invCnt;

}





int main() {

//code

int arr[]={2, 4, 1, 3, 5};

int n = sizeof(arr)/sizeof(arr[0]);

unsigned int cnt = mergeSort(arr,n);

printf(" Number of inversions are %d \n", cnt);

ifstream inputFile("IntegerArray.txt");

//ifstream inputFile("IntegerArray0.txt");

string line;

vector<int> ivec;

if(inputFile.is_open()){

while(getline(inputFile, line))

ivec.push_back(stoi(line));

           inputFile.close();

}



cout<<"number of item="<<ivec.size()<<endl;

int *p = new int[ivec.size()];

        //int p[100000];

        for(int i =0; i < ivec.size(); ++i)

p[i]=ivec[i];

        cnt = mergeSort(p, ivec.size());

printf(" 2: Number of inversions are %d \n", cnt);

unsigned int key=2407905288;

cout<<"cnt="<<cnt << " key shoud be : 2407905288 ="<< key <<endl;

        delete [] p;

return 0;

}

'via Blog this'