Inversion count in an array Merge Sort
unknown
java
a year ago
1.4 kB
6
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