DAA Assignment 1 Part 3

count_inversions.cpp

// C++ program for Assignment 1 Question 8
// We will count inversions using merge sort algorithm 
// and divide and conquer paradigm 
#include <bits/stdc++.h> 
using namespace std; 
  
long long _mergeSort(long long original_array[], long long arbitrary_array[], 
                     long long left_index, long long right_index); 
long long merge(long long original_array[], long long arbitary_array[], 
                long long left_index, long long mid_index, long long right_index); 
  
/* This is our recursive function which will divide the array in two halves 
then merge them in a sorted sequence while sorting it will also count inversions 
iff ith is smaller than jth and value of ith is greater jth */
long long _mergeSort(long long orignial_array[], long long arbitary_array[], 
                     long long left_index, long long right_index) 
{ 
    long long mid_index, inversions = 0; 
    if (left_index < right_index) { 
        /* mid index for dividing array into two halves */
        mid_index = round((right_index + left_index) / 2); 
        // Step A Divide the problem into sub problems
        // inversions from left half
        inversions = _mergeSort(orignial_array, arbitary_array, left_index, mid_index); 
        // inversions from right half
        inversions += _mergeSort(orignial_array, arbitary_array, mid_index + 1, right_index); 
  
        // solve all sub problems and merge them into one solution for original problem
        /*inversions during merge process*/
        inversions += merge(orignial_array, arbitary_array, left_index, mid_index + 1, right_index); 
    } 
    return inversions; 
} 
  
/* Will sort, merge and count the inversions in this part */
long long merge(long long orignial_array[], long long arbitary_array[], long long left_index, 
          long long mid_index, long long right_index) 
{ 
    long long i, j, k; 
    long long inversions_count = 0; 
  
    i = left_index; /* i is a ptr for left array*/
    j = mid_index; /* j is a ptr for right array*/
    k = left_index; /* k is a ptr for resultant merged array*/
    while ((i <= mid_index - 1) && (j <= right_index)) { 
        if (orignial_array[i] <= orignial_array[j]) { 
            arbitary_array[k++] = orignial_array[i++]; 
        } 
        else { 
            arbitary_array[k++] = orignial_array[j++];
            /* This is the part we are interested in if we are talking about inversions
            because we know that inversions are of pointer i is less than pointer j AND 
            value at pointer i is greater than the value at pointer j.
            Now if you look closesly our pointers are at correct condition because 
            the pointer i is starting from most left part probably 0 and 
            pointer j is starting from mid so our first condition and the second condition both satisfied. */
            inversions_count = inversions_count + (mid_index - i); 
        } 
    } 
  
    /* Handle the remaining elements from left array if there are any*/
    while (i <= mid_index - 1) 
        arbitary_array[k++] = orignial_array[i++]; 
  
    /* Handle the remaining elements from right array if there are any*/
    while (j <= right_index) 
        arbitary_array[k++] = orignial_array[j++]; 
  
    /*
        In the above part we were conquering the sub problems and now its time to combine them all 
        for getting the solution of our main problem
    */
    for (i = left_index; i <= right_index; i++) 
        orignial_array[i] = arbitary_array[i]; 
  
    return inversions_count; 
} 

int main() 
{ 
    long long size_of_n = 0;
    string line;
    string fileName = "IntegerArray.txt";
    ifstream ifileStream;
    ifileStream.open(fileName);
    if (ifileStream.is_open())
    {
        while ( getline (ifileStream,line) )
        {
            size_of_n++;
        }
        ifileStream.close();
        long long data[size_of_n];
        size_of_n = 0;
        ifileStream.open(fileName);
        if (ifileStream.is_open())
        {
            while ( getline (ifileStream,line) )
            {
                data[size_of_n] = std::stoi(line);
                size_of_n++;
            }
            ifileStream.close();
            long long temp_arr[size_of_n]; 
            long long total_inversions = _mergeSort(data, temp_arr, 0, size_of_n - 1); 
            cout << "Size of n is " + std::to_string(size_of_n) << endl;
            cout << "Number of inversions are "<<total_inversions<<endl;
        }else{
            cout << "Unable to open file "<<fileName<<endl;
        } 
    }else{
        cout << "Unable to open file "<<fileName<<endl;
    }
    return 0; 
}