CC-13 : Given an unsorted array find the ascending sort inversion count of the same.
Description:
Inversion count is a measure of how far the array is from being sorted. Two array elements form an inversion if idx1 < idx2 and arr[idx1] > arr[idx2]. We need to find all inversion pairs for given input array.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
| arr={4,3,2,1}
|
[4,3][4,2][4,1][3,2][3,1][2,1]
Count=6
|
| arr={1,2,3,4}
|
None
Count=0
|
| arr={3,4}
|
None
Count=0
|
Pseudocode:
| The java method should accept following input parameters: int array arr1.
|
| Initialize int variable inversionCount to 0.
|
| Iterate through arr using for loop with index idx1 from 0 to arr.length-1:
Iterate through arr using a for loop with index idx2 from idx1+1 to arr.length-1:
If (arr[idx1] > arr[idx2] ) we have found a inversion pair, we can print it and also increment inversionCount by 1.
|
| At end of above loops print the inversionCount of the array.
|
Code:
public static void arrayCountInversions(int[] arr) throws Exception{
int inversionCount=0;
boolean firstPair=true;
System.out.println("*****************************************************************************");
System.out.print("Inversion Pairs : ");
for (int idx1=0; idx1< arr.length; idx1++) {
for (int idx2=idx1+1; idx2< arr.length; idx2++) {
if (arr[idx1]>arr[idx2]) {
if (firstPair=true) {firstPair=false;}
else {System.out.print(" , ");}
inversionCount++;
System.out.print("["+arr[idx1]+","+arr[idx2]+"]");
}
}
}
System.out.println();
System.out.println("*****************************************************************************");
System.out.print("\nCount of Inversion Pairs : "+inversionCount+"\n\n");
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class ArrayCountInversions {
public static void arrayCountInversions(int[] arr) throws Exception{
int inversionCount=0;
boolean firstPair=true;
System.out.println("*****************************************************************************");
System.out.print("Inversion Pairs : ");
for (int idx1=0; idx1< arr.length; idx1++) {
for (int idx2=idx1+1; idx2< arr.length; idx2++) {
if (arr[idx1]>arr[idx2]) {
if (firstPair=true) {firstPair=false;}
else {System.out.print(" , ");}
inversionCount++;
System.out.print("["+arr[idx1]+","+arr[idx2]+"]");
}
}
}
System.out.println();
System.out.println("*****************************************************************************");
System.out.print("\nCount of Inversion Pairs : "+inversionCount+"\n\n");
}
public static void main(String[] args) {
try {
int[] intArray1 = {4,3,2,1};
printArraySummary(intArray1, "Original Array:");
arrayCountInversions(intArray1);
int[] intArray2 = {1,2,3,4};
printArraySummary(intArray2, "Original Array:");
arrayCountInversions(intArray2);
int[] intArray3 = {0,0,0};
printArraySummary(intArray3, "Original Array:");
arrayCountInversions(intArray3);
int[] intArray4 = {9,9};
printArraySummary(intArray4, "Original Array:");
arrayCountInversions(intArray4);
int[] intArray5 = {3,4};
printArraySummary(intArray5, "Original Array:");
arrayCountInversions(intArray5);
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex< intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}