Finding number of inversions in given array

Question

I have written the following code to find the inversions in array {1,4,2,5,3} by using merge sort technique. I have been debugging it to the best of my knoledge but I am not able to find out my mistake (as the output is not expected). Kindly help.

Please note: this is done for educational purposes and is not part of any ongoing contest.

My code:

#include<iostream>
#include<vector>
using namespace std;


int merge(int *arr,int l,int m,int r,int n)
{
    int temp[n];
    long long count =0;
    int i=l;
    int j=m+1;
    while(i<=m and j<=r)
    {
        if (arr[i-1]>arr[j-1])
        {
            count += m-i+1;
            temp[i+j-m-2] = arr[j-1];
            j++;
        }
        else
        {
            temp[i+j-m-2] = arr[i-1];
            i++;
            
        }
    }
    if (i>m)
    {
        for (int k=j;k<=r;k++)
            temp[k-1] = arr[k-1];
    }
    else
    {
        for (int k=i;k<=m;k++)
            temp[k-1] = arr[k-1];
            
    }

    for (int k=l;k<=r;k++)
        arr[k-1] = temp[k-1];
    return count;
    

}

int inversions(int *arr, int l,int r,int n)
{
    if (l<r)
    {
        int m=(l+r)/2;
        return inversions(arr,l,m,n)+inversions(arr,m+1,r,n)+merge(arr,l,m,r,n);
    }
    return 0;
}

int main()
{
    int arr[5] = {1,4,2,5,3};
    cout<<inversions(arr,1,5,5)<<endl;
    for (int i=1;i<=5;i++)
        cout<<arr[i-1]<<" ";
    return 0;
}

My expected output:

3
1 2 3 4 5

Actual output

2
1 4 2 5 0

What's your expected output? Your parameters are so poorly named, it's hard to know what they represent. One potential issue could be that you're passing 1 as a lower bound when you first call the function in main. C++ starts counting from 0. Your variable `i` is also completely unnecessary from what I can tell. Just use `l`. — sweenish, Oct 16 '20 at 17:05
not the problem but `int temp[n];` is not standard C++ (see [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard)). Using a container instead of raw array would make your code much simpler. — 463035818_is_not_an_ai, Oct 16 '20 at 17:07
`return inversions(arr,l,m,n)+inversions(arr,m+1,r,n)+merge(arr,l,m,r,n);` is not good because order of evaluation is not specified and `merge` can be executed before `inversions`. There seems be some other errors though. — MikeCAT, Oct 16 '20 at 17:09
@idclev463035818, I haven't used temp as a variable array but as usual array, because n has been treated as a constant inside the function. — Aradhye Agarwal, Oct 16 '20 at 17:11
`temp` is not a "usual" array! It is a variable length array that does not exist in standard C++. Some compilers provide it as an extension, though you don't need it because C++ has `std::vector` — 463035818_is_not_an_ai, Oct 16 '20 at 17:12
btw my comment above was two independent statements. Using VLAs is fine, you just should be aware that it isnt standard C++ (and maybe consider why you want to write non-standard code). The second point is that what makes your code complicated is the use of indices. I tried to check of out-of-bounds access but I wasnt able to verify that is it ok or not and I expect that using a container and iterators would be much simpler — 463035818_is_not_an_ai, Oct 16 '20 at 17:16

score -1 · Answer 1 · answered May 04 '22 at 14:37

-1

I am very interested in C++ so I am learning it. It's already 1 year learning C++ so I think I could help you. You Have many mistakes but I noticed The actual mistake It's the actual output. I used this code only in educational purposes and that's the mistake. Your actual output is not correct The actual actual output is: 2 1 4 2 5 264755412

So you can check again your code to see your mistake. Best REGARDS from Tigran. Country: Armenia | Region: Yerevan

answered May 04 '22 at 14:37

Tigran From Armenia

1

As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community May 07 '22 at 04:19

Finding number of inversions in given array

1 Answers1