geeksForGeeksSolutions/inversionOfArray.cpp at master · kk77777/geeksForGeeksSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends

// Function to find inversion count in the array

// arr[]: Input Array
// N : Size of the Array arr[]

#define ll long long

ll merge(ll arr[], ll l, ll r, ll mid, ll temp[])
{
    ll i, j, k;
    ll inv_cnt = 0;
    i = l, j = mid, k = l;
    while ((i <= mid - 1) && (j <= r))
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            inv_cnt += (mid - i);
        }
    }
    while (i < mid)
    {
        temp[k++] = arr[i++];
    }
    while (j <= r)
    {
        temp[k++] = arr[j++];
    }
    for (int i = l; i <= r; i++)
    {
        arr[i] = temp[i];
    }
    return inv_cnt;
}

ll mergeSort(ll arr[], ll l, ll r, ll temp[])
{
    ll mid, inv_cnt = 0;
    if (l < r)
    {
        mid = (l + r) / 2;
        inv_cnt += mergeSort(arr, l, mid, temp);
        inv_cnt += mergeSort(arr, mid + 1, r, temp);
        inv_cnt += merge(arr, l, r, mid + 1, temp);
    }
    return inv_cnt;
}

long long int inversionCount(long long arr[], long long N)
{
    // Your Code Here
    ll temp[N];
    ll ans = mergeSort(arr, 0, N - 1, temp);
    return ans;
}

// { Driver Code Starts.

int main()
{

    long long T;
    cin >> T;

    while (T--)
    {
        long long N;
        cin >> N;

        long long A[N];
        for (long long i = 0; i < N; i++)
        {
            cin >> A[i];
        }

        cout << inversionCount(A, N) << endl;
    }

    return 0;
}
// } Driver Code Ends