From 8e42c78e2f389f8aabefef163f38a54d170018b5 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Tue, 27 Nov 2018 08:43:56 -0600 Subject: Inversion count done! Pretty challenging but a lot of fun and very satisfying. Decided to implement MergeSort first without worrying about inversion count, then went from there. Lesson learned: use the debugger! :) Also passing by reference in Java can be convenient.--- .../sources/InversionCount.java | 109 +++++++++++++++++++++ .../tests/InversionCountTest.java | 50 ++++++++++ 2 files changed, 159 insertions(+) create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/InversionCount.java create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/InversionCountTest.java diff --git a/AlgoDesignAndTechniqueEdxJava/sources/InversionCount.java b/AlgoDesignAndTechniqueEdxJava/sources/InversionCount.java new file mode 100644 index 0000000..dd678fc --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/sources/InversionCount.java @@ -0,0 +1,109 @@ +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import java.util.Scanner; +import java.util.stream.Collectors; + +public class InversionCount { + + public static void main(String[] args) { + Scanner scanner = new Scanner(System.in); + int n = scanner.nextInt(); + int[] a = new int[n]; + for (int i = 0; i < n; i++) { + a[i] = scanner.nextInt(); + } +// int[] b = new int[n]; + System.out.println(getInversionCountFromArray(a)); + scanner.close(); + } + + public static long getNumberOfInversions(int[] a, int[] b, int left, int right) { + long numberOfInversions = 0; + if (right <= left + 1) { + return numberOfInversions; + } + int middle = (left + right) / 2; + numberOfInversions += getNumberOfInversions(a, b, left, middle); + numberOfInversions += getNumberOfInversions(a, b, middle, right); + // write your code here + return numberOfInversions; + } + + public static long getInversionCountFromArray(int[] a) { + List aList = Arrays.stream(a).boxed().collect(Collectors.toList()); + List D = new ArrayList(); + long numberOfInversions = getInversionCountFromList(aList, D); + return numberOfInversions; + } + + private static long getInversionCountFromList(List A, List D) { + long numberOfInversions = 0; + if (A.size() == 1) { + D.add(A.get(0)); + return 0; + } + int m = A.size() / 2; + List D1 = new ArrayList(); + numberOfInversions += getInversionCountFromList(new ArrayList(A.subList(0, m)), D1); + List D2 = new ArrayList(); + numberOfInversions += getInversionCountFromList(new ArrayList(A.subList(m, A.size())), D2); +// long mergeCount = mergeInversionCount(new ArrayList(A.subList(0, m)), new ArrayList(A.subList(m, A.size()))); + long mergeCount = mergeInversionCount(D1, D2, D); + return numberOfInversions + mergeCount; + } + + private static long mergeInversionCount(List B, List C, List D) { + long count = 0; + while (B.size() != 0 && C.size() != 0) { + int b = B.get(0); + int c = C.get(0); + if (b <= c) { + D.add(b); + B.remove(0); + } else { + count += B.size(); + D.add(c); + C.remove(0); + } + } + D.addAll(B); + D.addAll(C); + return count; + } + + public static int[] mergeSortArray(int[] a) { + List aList = Arrays.stream(a).boxed().collect(Collectors.toList()); + List sortedList = mergeSortList(aList); + return sortedList.stream().mapToInt(i -> i).toArray(); + } + + private static List mergeSortList(List A) { + if (A.size() == 1) + return A; + int m = A.size() / 2; + List B = mergeSortList(new ArrayList(A.subList(0, m))); + List C = mergeSortList(new ArrayList(A.subList(m, A.size()))); + List aPrime = mergeList(B, C); + return aPrime; + } + + private static List mergeList(List B, List C) { + List D = new ArrayList<>(); + while (B.size() != 0 && C.size() != 0) { + int b = B.get(0); + int c = C.get(0); + if (b <= c) { + D.add(b); + B.remove(0); + } else { + D.add(c); + C.remove(0); + } + } + D.addAll(B); + D.addAll(C); + return D; + } + +} diff --git a/AlgoDesignAndTechniqueEdxJava/tests/InversionCountTest.java b/AlgoDesignAndTechniqueEdxJava/tests/InversionCountTest.java new file mode 100644 index 0000000..483cd23 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/tests/InversionCountTest.java @@ -0,0 +1,50 @@ +import static org.junit.jupiter.api.Assertions.*; + +import org.junit.jupiter.api.Test; + +class InversionCountTest { + + @Test + void testInversionCount0() { + int[] a = {2, 3, 9, 2, 9}; + assertEquals(2, InversionCount.getInversionCountFromArray(a)); + } + + @Test + void testInversionCount1() { + int[] a = {1, 1, 1, 1, 1}; + assertEquals(0, InversionCount.getInversionCountFromArray(a)); + } + + @Test + void testInversionCount2() { + int[] a = {6, 5, 4, 3, 2, 1}; + assertEquals(15, InversionCount.getInversionCountFromArray(a)); + } + + @Test + void testInversionCount3() { + int[] a = {1, 1, 1, 2, 1}; + assertEquals(1, InversionCount.getInversionCountFromArray(a)); + } + + @Test + void testInversionCount4() { + int[] a = {2, 1, 1}; + assertEquals(2, InversionCount.getInversionCountFromArray(a)); + } + + @Test + void testMergeSort0() { + int[] a = {2, 3, 9, 2, 9}; + int[] b = {2, 2, 3, 9, 9}; + assertArrayEquals(b, InversionCount.mergeSortArray(a)); + } + + @Test + void testMergeSort1() { + int[] a = {5, 4, 3, 2, 1}; + int[] b = {1, 2, 3, 4, 5}; + assertArrayEquals(b, InversionCount.mergeSortArray(a)); + } +} -- cgit v1.2.3