1) Objective Your goal is to provide the program that will enable you to make use of mergesort to solve a seemingly  unrelated problem

Subject:Computer SciencePrice: Bought3

Share With

1) Objective

Your goal is to provide the program that will enable you to make use of mergesort to solve a seemingly 
unrelated problem. 

2. Problem

You have been asked to find the number of inversions in an array. An inversion is when a larger number appears before a smaller number. In the follow example, there are 3 inversions. 
[3, 2, 1]

1. 3 before 2

2. 3 before 1

3. 2 before 1 

You need to write two different algorithms to solve this problem. One is "slow". It is the naïve approach using nested loops. The "fast" approach uses a modified mergesort that counts the number of inversions and returns that count. Your program will always run the fast algorithm unless the user specifies "slow" as the (only) command-line argument. 

 

Here are some examples of how the program should run: 
$ java InversionCounter lots of args 
Usage: java InversionCounter [slow] 
$ java InversionCounter blazing Error: 
Unrecognized option 'blazing'. 

 

$ java InversionCounter 
Enter sequence of integers, each followed by a space: x 1 2 3 
Error: Invalid character 'x' found at index 4 in input stream. 
$ java InversionCounter 
Enter sequence of integers, each followed by a space: <some spaces> Error: 
Sequence of integers not received. 

$ java InversionCounter slow 
Enter sequence of integers, each followed by a space: 1 1 1 1 
Number of inversions: 0 
$ java InversionCounter 
Enter sequence of integers, each followed by a space: 3 1 0 1 2 9 
Number of inversions: 5

 

3. Requirements

You must use the following mergesort algorithm; very few changes are required to make mergesort count inversions. The code is provided below: 

private static void mergesortHelper(int[] array, int[] scratch, int low, int high) {         
if (low < high) {              int mid = low + (high - low) / 2;             
mergesortHelper(array, scratch, low, mid);             
mergesortHelper(array, scratch, mid + 1, high);  
  
            int i = low, j = mid + 1;             
for (int k = low; k <= high; k++) {                  if (i <= mid && (j > high || array[i] <= array[j])) {                     
scratch[k] = array[i++];                  } else {                      scratch[k] = array[j++];  
                }             
}              for (int k = low; k <= high; k++) {                 
array[k] = scratch[k];  
            }          }  
    }   
    public static void mergesort(int[] array) {         
int[] scratch = new int[array.length];  
        mergesortHelper(array, scratch, 0, array.length - 1);     
}

 

Note that both methods must return a long. It is ideal to produce the slow version that compiles in at most 8 seconds and the fast version that compiles in 1.25 seconds. I have started a solution thus, and need help with the TODO sections:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Class with two different methods to count inversions in an array of integers.

 */
public class InversionCounter {

    /**
     * Returns the number of inversions in an array of integers.
     * This method uses nested loops to run in Theta(n^2) time.
     * @param array the array to process
     * @return the number of inversions in an array of integers
     */
    public static long countInversionsSlow(int[] array) {
        // TODO
         
    }

    /**
     * Returns the number of inversions in an array of integers.
     * This method uses mergesort to run in Theta(n lg n) time.
     * @param array the array to process
     * @return the number of inversions in an array of integers
     */
    public static long countInversionsFast(int[] array) {
        // Make a copy of the array so you don't actually sort the original
        // array.
        int[] arrayCopy = new int[array.length],
              scratch =  new int[array.length];
        System.arraycopy(array, 0, arrayCopy, 0, array.length);
        // TODO - fix return statement
        return 0;
    }

    /**
     * Reads an array of integers from stdin.
     * @return an array of integers
     * @throws IOException if data cannot be read from stdin
     * @throws NumberFormatException if there is an invalid character in the
     * input stream
     */
    private static int[] readArrayFromStdin() throws IOException,
                                                     NumberFormatException {
        List<Integer> intList = new LinkedList<>();
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in));
        int value = 0, index = 0, ch;
        boolean valueFound = false;
        while ((ch = reader.read()) != -1) {
            if (ch >= '0' && ch <= '9') {
                valueFound = true;
                value = value * 10 + (ch - 48);
            } else if (ch == ' ' || ch == 'n' || ch == 'r') {
                if (valueFound) {
                    intList.add(value);
                    value = 0;
                }
                valueFound = false;
                if (ch != ' ') {
                    break;
                }
            } else {
                throw new NumberFormatException(
                        "Invalid character '" + (char)ch +
                        "' found at index " + index + " in input stream.");
            }
            index++;
        }

        int[] array = new int[intList.size()];
        Iterator<Integer> iterator = intList.iterator();
        index = 0;
        while (iterator.hasNext()) {
            array[index++] = iterator.next();
        }
        return array;
    }

    public static void main(String[] args) {
        // TODO
    }
}