HackerRank Algorithm Challenge 1: Insertion sort

Question

This is my solution for HackerRank's first "Algorithm Challenge, Insertion Sort Part 1". The challenge is to sort the array from least to greatest, the input being an array in sorted order, except for the last entity, i.e. {2, 3, 4, 5, 6, 7, 8, 9, 1}

It works fine, but it's definitely not an optimal solution. Could anybody provide any insights on how I should look at it so as to optimize it? This is for learning purposes, so I can apply the same concepts to future code.

   static void insertionSort(int[] ar) {
          int i, j;
          int inserted = 0;
          i = ar[ar.length-1];

          for (j = ar.length-2; j > -1; j--){
              if (ar[j] > i){
                  ar[j+1] = ar[j];
                  printArray(ar);
              } else if (ar[j] <= i){
                  ar[j+1] = i;
                  inserted = 1;
                  break;
              }   
          }

          if(inserted == 0){
              ar[0] = i;
          }

          printArray(ar);     
   }

This is the rest of the code, but it's preset and is already available:

 static void printArray(int[] ar) {
     for(int n: ar){
        System.out.print(n+" ");
     }
       System.out.println("");
  }

  public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       int[] ar = new int[n];
       for(int i=0;i<n;i++){
          ar[i]=in.nextInt(); 
       }
       insertionSort(ar);
   }    

Answer 1

Two components in particular are unnecessary. This test:

        } else if (ar[j] <= i){ 

is redundant. else means if (ar[j] <= i), since the latter is the negation of the earlier if (ar[j] > i).

And then, the inserted variable is used to track whether i was inserted within the loop. To simplify, I'd only do it outside the loop -- we can do this because j is still useful. (If you're not using j outside the loop, as in your original code, it's better -- safer, more readable -- style to declare it in the for statement.)

This is the heart of what you're doing:

static void insertionSort(int[] ar) {
    int i, j;
    i = ar[ar.length-1];

    for (j = ar.length-2; j > -1; j--){
        if (ar[j] > i){
            ar[j+1] = ar[j];
            printArray(ar);
        } else {
            break;
        }   
    }
    ar[j+1] = i;
    printArray(ar);
}

Or:

static void insertionSort(int[] ar) {
    int i = ar[ar.length-1];
    int j;
    for (j = ar.length-2; (j >= 0) && (ar[j] > i); j--) {
        ar[j+1] = ar[j];
        printArray(ar);
    }
    ar[j+1] = i;
    printArray(ar);
}

There are some style quibbles, but that's the big stuff. I'd take the printing out of it, except that the purpose of this function doesn't seem to be "perform an insertion sort", but rather "show how an insertion sort inserts an element". I don't see any advantage to using a binary search, since that only helps you find the insertion point, and you still need to iterate over all elements > ar[i] to move their values.

Answer 2

You could binary search the list (without the last element) to get the new position of the last element. The JDK already has a method for that but you can write your own too for practice.

Some other notes:

1. int i, j;
   

   I'd put the variable declarations to separate lines. From Code Complete, 2nd Edition, p759:

   With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

2. About the j variable: Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

   int i = ar[ar.length - 1];
   
   for (int j = ar.length - 2; j > -1; j--) {
       ...
   

3. I would use longer variable names than ar. Longer names would make the code more readable since readers don't have to decode the abbreviations every time and when they write/maintain the code don't have to guess which abbreviation the author uses: Was it a? ar? arr? (It's a bigger problem in more complex cases.)

   Furthermore, i could be newElement. It would be easier to read.

4. The sort method should validate its input parameter. Does it make sense to call it with null? If not, check it and throw a NullPointerException. Currently it throws an ArrayIndexOutOfBoundsException when it's been called with an empty array. It should throw an exception (IllegalArgumentException) with better error message. (Effective Java, Second Edition, Item 38: Check parameters for validity)

5. Currently the insertionSort method violates the Single responsibility principle. It sorts the array and prints the array. If a client wants to print the array they should call the print method. It should not be in the sort method.

6. The inserted integer could be a boolean. It would be less error prone (booleans have only two states, not 2^32).