Inversion count in an array Merge Sort
unknown
java
a year ago
1.4 kB
10
Indexable
public class DivideandConquer_inversion_count {
static int count = 0;
public static int[] countInversion(int[] arr,int si,int ei){
if(si == ei){
int[] ba = new int[1];
ba[0] = arr[si];
return ba;
}
int mid = si+(ei-si)/2;
int[] left = countInversion(arr,si,mid);
int[] right = countInversion(arr,mid+1,ei);
int[] res = mergeTwoSortedArrays(left,right);
return res;
}
public static int[] mergeTwoSortedArrays(int[] left, int[] right){
int n = left.length;
int m = right.length;
int[] res = new int[n+m];
int i=0;
int j=0;
int k=0;
while (i<n && j<m){
if(left[i] < right[j]){
res[k] = left[i];
i++;
}else {
res[k] = right[j];
count += (n-i);
j++;
}
k++;
}
while (i<n){
res[k] = left[i];
i++;
k++;
}
while (j<m){
res[k] = right[j];
j++;
k++;
}
return res;
}
public static void main(String[] args) {
int[] arr = {4,1,7,2,9,5};
int[] res = countInversion(arr,0,5);
System.out.println(count);
}
}
Editor is loading...
Leave a Comment