Sorting in Java - Part 2

This is part 2 in the series. It is suggested to read the whole series from the beginning.

• Part 1

Insertion Sort

It is one of the simplest sorting algorithm and the idea is straight forward. And it is a more human way of sorting. Alright, bubble sort is also simple to code but few humans would actually use bubble sort to sort physical objects in real world. Since Insertion Sort is more human-like and therefore it would be more easy to understand, so we will first implement this algorithm.

Algorithm

For any unsorted arrays, split it into two lists, one is known as the sorted list, the other is the unsorted list, initially the sorted list contains no element. Repeat the following :

• Pick an element from the unsorted list, this is the insertionElement.
• Scan from the end of the sorted list, until the correct position for the insertion element is found.
• Insert the element at the correct position

During the scanning process, the entries in the sorted list is shifted to the right one by one to make room for the insertionElement.

Insertion Sort in Action

As I said, Insertion Sort is a more human way of sorting. So let's look at a real life example. Suppose we are playing the game of Mahjong. And we have a list of four sorted tiles in front of us. We draw a new tile, the five of circle from the closed tiles (think of it as an unsorted list).

Pick an element from the unsorted list, this is the insertionElement.

Scan from the end of the sorted list, until the correct position for the insertion element is found.

Insert the element at the correct position

Source code

The following is a straight forward implementation.

/******************************************************************************
* File : InsertionSort.java
* Author : http://java.macteki.com/
* Description :
*   Demonstration of Insertion Sort
* Tested with : JDK 1.6
******************************************************************************/

class InsertionSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }

  public static void insertionSort(int[] a)
  {
    // i=size of the sorted list, it is increased by 1 for every pass
    for (int i=0;i<a.length;i++) 
    {
      int element=a[i];    // get an element from the unsorted list
      int j=i;             // j : the scanning pointer
      for (j=i;j>=1;j--)   // scan backwards from the end of the sorted list
      {
        if (element<a[j-1]) // not the correct position yet
        {
            a[j]=a[j-1];    // shift to the right to make room for element
        }
        else break;     // correct position found, break the scanning loop
      }                 
      a[j] = element;   // insert element in the correct position
    } // loop for next i, the sorted list size will be increased by 1
  }

  public static void main(String[] args) throws Exception
  {
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    insertionSort(a);    
    
    printArray(a);
  }
}