Insertion Sort Algorithm using Generics in Java

Today, we are going to show the implementation of the Insertion Sort, which is the second algorithm of our series of tutorials on sorting algorithms. If you haven’t read the first tutorial on BubbleSort, I strongly recommend that you go there and read it, because we will reuse code that was explained there.

The application is really simple, it will just get an instance of a Sortable algorithm, which in this case will be an InsertionSort object and pass some Integer and String arrays to it, but any object that implements Comparable can be passed as a parameter as well, then it will print the elements from the arrays.

public class SorterApp {
  public static void main(String[] args) {
    SorterApp app = new SorterApp();
    app.run();
  }

  private void run() {
    sort(new Integer[] { 1, 2, 3, 4, 5 });
    sort(new Integer[] { 3, 1, 5, 4, 2 });
    sort(new Integer[] { 5, 4, 3, 2, 1 });

    System.out.println();

    sort(new String[] { "a", "b", "c", "d", "e" });
    sort(new String[] { "c", "a", "e", "d", "b" });
    sort(new String[] { "e", "d", "c", "b", "a" });
  }

  private <T extends Comparable<T>> void sort(T[] values) {
    Sortable sorter = newSortable(2);
    sorter.sortAscending(values);
    // sorter.sortDescending(values);
    Utils.printArray(values);
  }

  private Sortable newSortable(int sortableAlgorithm) {
    switch (sortableAlgorithm) {
      case 1:
        return new BubbleSort();
      case 2:
        return new InsertionSort();
      default:
        return new BubbleSort();
    }
  }
}

You can see on the code below that the sortAscending and sortDescending invoke the same method sort with the difference of just 2 parameters. This is done because the code to sort in ascending or descending order is pretty much the same, the difference is just one small detail.

The Sorter Abstract class and the Sortable Interface were explained on the previous tutorial.

public class InsertionSort extends Sorter implements Sortable {
  @Override
  public <T extends Comparable<T>> void sortAscending(T[] values) {
    sort(values, 0, 1);
  }

  @Override
  public <T extends Comparable<T>> void sortDescending(T[] values) {
    sort(values, 1, 0);
  }

The Insertion sort builds the final sorted array one item at a time. It is not very efficient on large lists but it is easy to implement.

  private <T extends Comparable<T>> void sort(T[] values, int first, int second) {
    if ((null == values) || (values.length < 2)) {
      return;
    }

    int length = values.length;
    int count = 0;
    int j;
    for (int i = 1; i < length; i++) {
      j = i;
      count++;
      while ((j > 0) &amp;&amp; (values[j - first].compareTo(values[j - second]) < 0)) {
        swap(values, j - first, j - second);
        j--;
        count++;
      }
    }
    System.out.printf("%2s: ", count);
  }
}

Results:

Insertion Sort Results

You can download all the files here: InsertionSort.

Thank you for your time and feel free to leave any comments or questions.

References:
http://en.wikipedia.org/wiki/Insertion_sort
http://www.youtube.com/watch?v=c4BRHC7kTaQ

Tweet about this on TwitterShare on StumbleUponShare on Google+Share on LinkedInShare on Facebook

3 Responses to “Insertion Sort Algorithm using Generics in Java”

  1. Selection Sort Algorithm using Generics in Java - The Code Master Says:

    […] Insertion Sort Algorithm using Generics in Java […]

  2. Counting Sort Algorithm in Java - The Code Master Says:

    […] on sorting algorithms. If you haven’t read the first three tutorials on BubbleSort, InsertionSort and SelectionSort, I strongly recommend that you read them, because we will reuse code that was […]

  3. Merge Sort Algorithm using Generics in Java - The Code Master Says:

    […] on sorting algorithms. If you haven’t read the first four tutorials on BubbleSort, InsertionSort, SelectionSort and CountingSort, I strongly recommend that you go there and read them, because […]

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.