Created
March 10, 2019 16:34
-
-
Save allanx2000/8ec2a786f7a18da9c9d4aa23818a8431 to your computer and use it in GitHub Desktop.
MergeSort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.math.*; | |
| import java.security.*; | |
| import java.text.*; | |
| import java.util.*; | |
| import java.util.concurrent.*; | |
| import java.util.regex.*; | |
| public class Solution { | |
| static long countInversions(int[] arr) | |
| { | |
| long inversionsCount = 0; | |
| int [] lowerArray = new int [arr.length]; | |
| int [] higherArray = new int [arr.length]; //frm mid+1 to high | |
| inversionsCount = countAndSort (arr, 0, arr.length - 1, lowerArray, higherArray); | |
| return inversionsCount; | |
| } | |
| static long countAndSort(int [] arr, int low, int high, int [] lowerArray, int [] higherArray) | |
| { | |
| long totalCount = 0; | |
| long count = 0; | |
| if (low < high) | |
| { | |
| int mid = low + (high-low) /2; | |
| long lowerCount = countAndSort (arr, low, mid, lowerArray, higherArray); | |
| long higherCount = countAndSort (arr, mid+1, high, lowerArray, higherArray); | |
| totalCount += lowerCount + higherCount + countAndSortMerge (arr, low, mid, high, lowerArray, higherArray); | |
| } | |
| return totalCount; | |
| } | |
| static long countAndSortMerge(int [] arr, int low, int mid, int high, int [] lowerArray, int [] higherArray) | |
| { | |
| long countInversions = 0; | |
| for (int i=0; i< (mid-low+1);i++) | |
| { | |
| lowerArray[i] = arr [low+i]; | |
| } | |
| for (int i=0; i< (high-mid);i++) | |
| { | |
| higherArray[i] = arr [mid+1+i]; | |
| } | |
| int lowIndex = 0; | |
| int highIndex = 0; | |
| int arrIndex = low; | |
| while (lowIndex < (mid-low+1) && highIndex < (high-mid)) | |
| { | |
| if (lowerArray[lowIndex] <= higherArray [highIndex]) | |
| { | |
| arr[arrIndex] = lowerArray[lowIndex]; | |
| ++lowIndex; | |
| } | |
| else | |
| { | |
| arr[arrIndex] = higherArray[highIndex]; | |
| ++highIndex; | |
| countInversions += (mid-low+1 - lowIndex); | |
| } | |
| ++arrIndex; | |
| } | |
| while (lowIndex < (mid-low+1)) | |
| { | |
| arr[arrIndex] = lowerArray[lowIndex]; | |
| ++lowIndex; | |
| ++arrIndex; | |
| } | |
| while (highIndex < (high-mid)) | |
| { | |
| arr[arrIndex] = higherArray[highIndex]; | |
| ++highIndex; | |
| ++arrIndex; | |
| } | |
| System.out.printf("CountandsortMerge inversions - %d", countInversions); | |
| return countInversions; | |
| } | |
| private static final Scanner scanner = new Scanner(System.in); | |
| public static void main(String[] args) throws IOException { | |
| BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); | |
| int t = scanner.nextInt(); | |
| scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); | |
| for (int tItr = 0; tItr < t; tItr++) { | |
| int n = scanner.nextInt(); | |
| scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); | |
| int[] arr = new int[n]; | |
| String[] arrItems = scanner.nextLine().split(" "); | |
| scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); | |
| for (int i = 0; i < n; i++) { | |
| int arrItem = Integer.parseInt(arrItems[i]); | |
| arr[i] = arrItem; | |
| } | |
| long result = countInversions(arr); | |
| bufferedWriter.write(String.valueOf(result)); | |
| bufferedWriter.newLine(); | |
| } | |
| bufferedWriter.close(); | |
| scanner.close(); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment