-
Notifications
You must be signed in to change notification settings - Fork 0
/
082_CountInversions.cpp
63 lines (48 loc) · 1.29 KB
/
082_CountInversions.cpp
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
#include<bits/stdc++.h>
using namespace std;
long long merge(long long *arr, int start, int mid, int end){
long long count=0;
int i=start, j=mid, k=0;
long long copy[end-start+1];
while(i<=mid-1 && j<=end){
if(arr[i]<=arr[j]){
copy[k++]=arr[i++];
}else{
copy[k++]=arr[j++];
count+=(mid-i); //count elements from mid to the start or i -> mid
}
}
while(i<=mid-1){
copy[k++]=arr[i++];
}
while(j<=end){
copy[k++]=arr[j++];
}
for(int s=start, p=0; s<=end; s++, p++){
arr[s]=copy[p];
}
return count;
}
long long mergeSort(long long *arr, int start, int end){
long long count=0;
if(start<end){
int mid=(start+end)/2;
count+=mergeSort(arr, start, mid);
count+=mergeSort(arr, mid+1, end);
count+=merge(arr, start, mid+1, end);
}
return count;
}
long long getInversions(long long *arr, int n){
// Write your code here.
// method-1
// long long count=0;
// for(int i=0; i<n; i++){
// for(int j=i+1; j<n; j++){
// if(arr[i]>arr[j]) count++;
// }
// }
// return count;
// method-2
return mergeSort(arr, 0, n-1);
}