-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcountInversion.java
More file actions
37 lines (29 loc) · 936 Bytes
/
countInversion.java
File metadata and controls
37 lines (29 loc) · 936 Bytes
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
public class countInversion {
static long inversionCount(long arr[], long N)
{
// Your Code Here; count inversions; try merge sort
// Split array, left right midpoint
long count = 0;
}
public static void main(String[] args) {
// long[] arr = {2, 4, 1, 3, 5};
// long N = 5;
// long[] arr = {2, 3, 4, 5, 6};
// long N = 5;
long[] arr = {10, 10, 10};
long N = 3;
System.out.println(inversionCount(arr, N));
}
}
/* This solution works but is O(N^2) so times out; use merge sort instead
* long count = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
count++;
System.out.println("i: " + i + ", j: " + j + ", count: " + count);
}
}
}
return count;
*/