Question

Develop and implement a linearithmic algorithm _{Inversions.java} for computing the number of inversions in a given array (the number of exchanges that would be performed by insertion sort for that array—see Section 2.1). This quantity is related to the Kendall tau distance.

Answer 1

The Code in Java:

import java.util.Scanner;

public class Inversions {
    public static void main(String[] args) {
        int array[] = {4,7,2,9,1};
        //the counter that will count the number of swaps during insertion sort
        int counter=0;
        int n = array.length;
        int temp,i,j;
        for (i = 1; i< n; i++)
        {
            j = i;
            temp = array[i];  
            while (j > 0 && temp < array[j-1])
            {
                array[j] = array[j-1];
                j = j-1;
                //swap found!
                counter++;
            }
            array[j] = temp;          
        }  
        //printing the counter out to the console
        System.out.println(counter);
    }  
}

Console Output: