Algorithm

HackerRank/Merge Sort/Counting Inversions

Problem Summary

Given an array of N integers, calculate the number of swaps you need to perfom to sort the array in ascending order. You can only swap adjacent elements.

Solution

We use merge sort to solve this problem. During each merging process, we count the number of swaps. And we get the sum recursively.

Note that we can only swap adjacent elements. So moving an integer from position j to position i requires i-j swaps.

A trick for saving time :
We can use two arrays A and B, to store the data, and if this time we perfom the merge function from A to B, the next time we perfom it from B to A. In this way we do not have to copy the array every time.

Code

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100010;
int n,arr[maxn],aux[maxn];
long long merge(int (&s)[maxn],int (&t)[maxn],int st,int mid,int en)
{
    int i = st, j = mid+1, idx = st;
    long long res = 0;
    while (i<=mid && j<=en)
    {
        if (s[i] <= s[j])
            t[idx++] = s[i++];
        else
        {
            t[idx++] = s[j++];
            res += mid+1 - i;
        }
    }
    while (i<=mid)
    {
        t[idx++] = s[i++];
    }
    while (j<=en)
    {
        t[idx++] = s[j++];
    }
    return res;
}
long long merge_sort(int (&s)[maxn],int (&t)[maxn],int st,int en)
{
    if (st >= en)
        return 0;
    long long count = 0;
    int mid = st + ((en-st)>>1);
    count += merge_sort (t,s,st,mid);
    count += merge_sort (t,s,mid+1,en);
    count += merge(s,t,st,mid,en);
    return count;
}
int main() {
    
    int Q;
    cin >> Q;
while (Q--)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        aux[i] = arr[i];
    }
    
    cout << merge_sort(arr,aux,0,n-1) << endl;
}
    return 0;
}