Insertion Sort Java

For each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.

Following video explains it clearly.

https://www.youtube.com/watch?v=i-SKeOcBwko

For example,

For the input 20, 5, 14, 19, 8, 17

Iteration 1: 5, 20, 14, 19, 8, 17 (Fix position of element 5)

Iteration 2: 5, 14, 20, 19, 8, 17 (Fix position of element 14)

Iteration 3: 5, 14, 19, 20, 8, 17 (Fix position of element 19)

Iteration 4: 5, 8, 14, 19, 20, 17 (Fix position of element 8)

Iteration 5: 5, 8, 14, 17, 19, 20 (Fix position of element 17)

Following is the generic program for insertion sort.

public class InsertionSort<T extends Comparable<T>> {

 /**
  * If flag is true, then elements are sorted in ascending order, else
  * descending order
  */
 public void sort(T[] arr, boolean flag) {
  if (flag == true)
   sortAscending(arr);
  else
   sortDescending(arr);
 }

 private void sortDescending(T[] arr) {

  for (int i = 1; i < arr.length; i++) {
   T temp = arr[i];
   int j;
   for (j = i - 1; j >= 0; j--) {
    if (temp.compareTo(arr[j]) > 0) {
     arr[j + 1] = arr[j];
    } else {
     break;
    }
   }
   arr[j + 1] = temp;
  }
 }

 private void sortAscending(T[] arr) {

  for (int i = 1; i < arr.length; i++) {
   T temp = arr[i];
   int j;
   for (j = i - 1; j >= 0; j--) {
    if (temp.compareTo(arr[j]) < 0) {
     arr[j + 1] = arr[j];
    } else {
     break;
    }
   }
   arr[j + 1] = temp;
  }
 }

}

Following is the junit test case for above program.

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class InsertionSortTest {

 @Test
 public void test1() {
  InsertionSort<Integer> obj1 = new InsertionSort<>();

  Integer arr1[] = { 5, 46, 25, 13, 12 };
  Integer arr2[] = { 5, 46 };

  obj1.sort(arr1, true);
  assertTrue(Arrays.equals(arr1, new Integer[] { 5, 12, 13, 25, 46 }));

  obj1.sort(arr1, false);
  assertTrue(Arrays.equals(arr1, new Integer[] { 46, 25, 13, 12, 5 }));

  obj1.sort(arr2, true);
  assertTrue(Arrays.equals(arr2, new Integer[] { 5, 46 }));

  obj1.sort(arr2, false);
  assertTrue(Arrays.equals(arr2, new Integer[] { 46, 5 }));
 }
}