Untitled
BlueDragon2707
java
2 years ago
1.6 kB
5
Indexable
package sort; public class CountInversionInArray { public static int merge(int[] arr, int l, int r, int m) { int res = 0; // int[] arr = {2,4,1,3,5}; int n1 = m - l + 1; int n2 = r - m; int left[] = new int[n1]; int right[] = new int[n2]; // filling left and right array for (int i = 0; i < n1; i++) left[i] = arr[i + l]; for (int i = 0; i < n2; i++) right[i] = arr[i + m + 1]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (left[i] <= right[j]) arr[k++] = left[i++]; else { arr[k++] = right[j++]; res = res + (n1 - i); // most important line } } while (i < n1) { arr[k++] = left[i++]; } while (j < n2) { arr[k++] = right[j++]; } return res; } public static int mergeSort(int[] arr, int l, int r) { int res = 0; if (l < r) { int m = (l + r) / 2; res = res + mergeSort(arr, l, m); res = res + mergeSort(arr, m + 1, r); res = res + merge(arr, l, r, m); } return res; } public static void main(String[] args) { int[] arr = { 2, 4, 1, 3, 5 }; // inversion: pair with numbers where greater number appear before smaller. // eg. (4,1) , (4,3) , (2,1) , o/p: 3 // int count = 0; // Naive Solution // for(int i=0; i<arr.length-1; i++) { // for(int j=i+1; j<arr.length; j++){ // // if(arr[i] > arr[j]) // count++; // // } // } // // System.out.println(count); // Efficient Solution: // use merge sort for efficient solution System.out.println(mergeSort(arr, 0, arr.length - 1)); } }
Editor is loading...