csfall11-insertionsort

Solution.java

/*
  Please write complete compilable code.
  Your class should be named Solution
  Read input from standard input (STDIN) and print output to standard output(STDOUT).
  For more details, please check http://www.interviewstreet.com/recruit/challenges/faq/view#stdio
*/

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        // scan is stdin
        Scanner scan = new Scanner(System.in);

        // get number of test cases and set up solution array
        int numCases = scan.nextInt();
        int[] output = new int[numCases];

        // iterate over each individual test case
        for (int currentCase = 0; currentCase < numCases; ++currentCase) {
            // Invariant: currentCase number of cases have been solved
            // prior to the execution of this loop

            // get the size of this case's array and initialize it'
            int N = scan.nextInt();
            int[] a = new int[N];

            // populate a with the next N integers
            for (int aIndex = 0; aIndex < N; ++aIndex) {
                a[aIndex] = scan.nextInt();
            }

            // initialize a counter for the number of swaps, then
            // insertion sort it
            int counter = 0;
            for (int i = 0; i < N; ++i) {
                int j = i;
                while (j > 1 && a[j] < a[j-1]) {
                    swap(a,j,j-1);
                    counter += 1;
                    j=j-1;
                }
            }

            // save the counter for this test case to solutions
            output[currentCase] = counter;
        }

        // print the output
        for (int line = 0; line <numCases; ++line) {
            System.out.println(output[line]);
        }
    }

    // swaps keys at index i and j in array a
    public static void swap(int[] a, int i, int j) {
        int temp = 0;
        a[i] = temp;
        a[i] = a[j];
        a[j] = temp;
    }
}