2

I am trying to count inversion(for eg.,for array [2,5,4,1] the inversion count is=4 namely (2,1),(5,4),(5,1),(4,1) using divide and conquer for a large set of arrays, I am getting a recursive count of value when a function executes each merge sort. I store all the count values in a vector and then again use sum operations, it works well for an array size of 70,000 but fails after it. I feel I am unnecessarily storing a large value to vector, instead, I am looking for a way to directly count the same but I am not getting a way to do the same, please help me in achieving it.

ps:the file link is this. my code looks like;

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
long long greater_v(long long *array,long long ap,long long p){
    long long numx=0;
    for(long long i=0;i<p;i++){
        if(array[i]>ap){
            numx++;
        }
    }
    return numx;
}
long long merge(long long U[],long long Lu,long long V[],long long Lv,long long S[],long long count1){
    long long uf=0;long long vf=0;
    for(long long sb=0;sb<Lu+Lv;sb++){
        if(uf<Lu && vf<Lv){
            if(U[uf]<V[vf]){
                S[sb]=U[uf];uf++;}
            else{
                S[sb]=V[vf];
               count1=count1+=greater_v(U,V[vf],Lu);
                
                vf++;
                

            }
        }
        else if(uf<Lu){
            S[sb]=U[uf];uf++;
        }
        else{
            S[sb]=V[vf];vf++;
        }
    }
return count1;
}

In this part I am looking for help where I am storing the value in the vector, instead, i want a way to directly count.

vector<unsigned long long int>v_val;
void MergeSort(long long arr[],long long n){
    long long count=0;
    //cout<<"sorting  ";print(arr,n);
    if(n==1)
        return;
    long long U[n/2];long long V[n-n/2];
    for(long long i=0;i<n/2;i++){
        U[i]=arr[i];
        }
    for(long long i=0;i<n-n/2;i++){
        V[i]=arr[i+n/2];
        }
    MergeSort(U,n/2);
    MergeSort(V,n-n/2);
    count+=merge(U,n/2,V,n-n/2,arr,count);
    v_val.push_back(count);
}

main function is;

int main(){
long long test_count=0;
    ifstream file_num("pr_as_2.txt");
    long long arr_num[100000];
    for(long long i=0;i<100000;i++){
        file_num>>arr_num[i];
    }


unsigned long long int sum_val=0;
   MergeSort(arr_num,70000);
   for(size_t i=0;i<v_val.size();i++){
       sum_val+=v_val[i];
   }
   cout<<sum_val;

}
def __init__
  • 1,092
  • 6
  • 17
  • 1
    You have some [*magic numbers*](https://en.wikipedia.org/wiki/Magic_number_(programming)) in your code. And they don't even match. What if there aren't `100000` values in the file? What if there are *more*? And what if there aren't even `70000` values in the file? – Some programmer dude Jun 20 '21 at 07:37
  • Also please take some time to refresh [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). ***How*** does your program "fail"? What happens? What is supposed to happen? And you do know that local variables (including arrays) are usually placed on the stack, and that the stack is limited in size (perhaps as little as 1MiB)? – Some programmer dude Jun 20 '21 at 07:39
  • @ some programmer dude Thank you so much sir, its 100% sure file has 100000 values, it's Stanford programming assignment, I calculated answer using brute force and I saw my optimised algorithm worked well for the value up to 70,000,might be I made error so it is not working further. – def __init__ Jun 20 '21 at 08:03
  • sir i have added in what part I am looking for help actually I have to store return count value of merge in vector for e.g mergesort(arr_num,10) output is 28 & my store value in vector is (4,1,1,2,2,1,1,2,3,15). i want to count these without storing it, as my code runs recursively i am confused to find a way to directly count these. – def __init__ Jun 20 '21 at 08:11
  • It looks like your `merge` function is supposed to return a `long long` but there isn't even a return statement in it. As a tip you should compile with warnings enabled. I'm surprised that the program works for small cases if the expected return value is not used at all. – wLui155 Jun 20 '21 at 08:21
  • @wLui155 apologies for missing it in the code sir, I have added it return count1. – def __init__ Jun 20 '21 at 08:26
  • By the way, if you had taken classes or read [good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) you should have known that `long long U[n/2];` [is not proper C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Don't use so-called "competition" sites to learn programming or programming languages, that's not what they're for. All example on such sites teach are bad habits which can make you virtually unemployable. – Some programmer dude Jun 20 '21 at 09:38

1 Answers1

1

look at this approach, it worked for me.

#include <bits/stdc++.h>

using namespace std;

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
unsigned int merge(int arr[], int temp[], int l, int m, int r) {
    unsigned int inversions = 0;
    int i = l;
    int j = m;
    int k = l;
    while (i < m && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
            inversions += m-i;
        }
        k++;
    }
    while (i < m) {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= r) {
        temp[k] = arr[j];
        j++;
        k++;
    }
    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }
    return inversions;
}

unsigned int count(int arr[], int temp[], int l, int r) {
    unsigned int inversions = 0;
    if (r > l) {
        int m = (r+l)/2;
        inversions = count(arr, temp, l, m);
        inversions += count(arr, temp, m+1, r);
        inversions += merge(arr, temp, l, m+1, r);
    }
    return inversions;
}

int main() {
    int arr_size = 100000;
    int arr[arr_size];
    ifstream file("IntegerArray.txt");
    string str;
    int i = 0;
    while (getline(file, str)) {
        arr[i] = stoi(str);
        i++;
    }
    // int arr[] = { 1, 20, 6, 4, 5 };
    // int arr_size = sizeof(arr) / sizeof(arr[0]);
    int temp[arr_size];
    /* mergeSort(arr, 0, arr_size-1);
    for (int i = 0; i < arr_size; i++) {
        cout << arr[i] << " ";
    } */
    cout << count(arr, temp, 0, arr_size-1) << endl;
}
Satya
  • 187
  • 1
  • 10
  • Please [don't use ``](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Not in your own code, and never in answers. Also, code-only answers without descriptions of how and why it solves the problem being asked about are rather bad and tend to promote [cargo cult programming](https://en.wikipedia.org/wiki/Cargo_cult_programming) which is bad. Please read or refresh [how to write good answers](https://stackoverflow.com/help/how-to-answer). – Some programmer dude Jun 20 '21 at 09:27