Question

sorting- Inversion Count for an array indicates

Language: c++

Your solution has to be O(n log n).

please write comments

*countinv.cpp*

// Count inversions - homework

// Based off of mergesort

#include <vector>

#include <algorithm> // For copy

using namespace std;

int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right) {

// You will need this helper function that calculates the inversion while merging

// Your code here

}

int countInv(vector<int>&nums) {

// Your code here

}

//test code

/* Count the number of inversions in O(n log n) time */

#include <iostream>

#include <vector>

using namespace std;

int countInv(vector<int>& numvec);

int main()

{

int n;

vector<int> numvec{4, 5, 6, 1, 2, 3};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 9

  

numvec = {1, 2, 3, 4, 5, 6};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 0

  

numvec = {6, 5, 4, 3, 2, 1};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 15

  

numvec = {0, 0, 0, 0, 0, 0};

n = countInv(numvec);

cout << "Number of inversions " << n << endl;; // Should be 0

}

*countinv_test.cpp*

/* Count the number of inversions in O(n log n) time */

#include <iostream>

#include <vector>

using namespace std;

int countInv(vector<int>& numvec);

int main()

{

int n;

vector<int> numvec{4, 5, 6, 1, 2, 3};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 9

  

numvec = {1, 2, 3, 4, 5, 6};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 0

  

numvec = {6, 5, 4, 3, 2, 1};

n = countInv(numvec);

cout << "Number of inversions " << n << endl; // Should be 15

  

numvec = {0, 0, 0, 0, 0, 0};

n = countInv(numvec);

cout << "Number of inversions " << n << endl;; // Should be 0

}

Answer 1

#include<bits/stdc++.h>
using namespace std;
int x;
int temp[1000];
void merge(vector <int> a, int l, int m,int r){ //Merge Algorithm
    int k=0;
    int i=l;
    int j=m+1;
    while(i<=m && j<=r){
        if (a[i]>a[j]){   //inversion
            temp[k]=a[j];
            j+=1;
            x+=m-i+1;
        }
        else{
            temp[k]=a[i];
            i+=1;
        }
        k+=1;
    }
    if(i>m){         //Copying remaining right half of array 
        while(j<=r){
            temp[k]=a[j];
            k+=1;
            j+=1;
        }
    }
    else{           //Copying remaining left half of array 
        while(i<=m){
            temp[k]=a[i];
            k+=1;
            i+=1;
        }
    }
    k=0;
    for(i=l;i<=r;i++){
        a[i]=temp[k];
        k+=1;
    }
}
void mergeSort(vector <int> a,int l,int r){ //Merge Sort Algorithm
    if (l<r){
        int m=(l+r)/2;
        mergeSort(a,l,m);
        mergeSort(a,m+1,r);
        merge(a,l,m,r);
    }
}
int countInv(vector<int> numvec){
    x=0;    //keeps track of no.of inversions
    mergeSort(numvec,0,numvec.size()-1);
    return x;
}
int main()
{

    int n;
    vector<int> numvec{4, 5, 6, 1, 2, 3};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 9
    numvec = {1, 2, 3, 4, 5, 6};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 0
    numvec = {6, 5, 4, 3, 2, 1};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 15
    numvec = {0, 0, 0, 0, 0, 0};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl;; // Should be 0
}