Insertion Sort

Part:   1  2 

This chapter helps you to understand:

• Basic Idea
• Java Implementation
• Performance
• Improvements

Basic Idea

The basic idea of Insertion Sort:

1. Data elements are grouped into two sections: a sorted section and an un-sorted section.

2. Take an element from the un-sorted section.

3. Insert the element into the sorted section at the correct position based on the comparable property.

4. Repeat step 2 and 3 until no more elements left in the un-sorted section.

The idea of insertion sort comes from our daily life experiences. For example, when you play cards with your friends, you will insert the next card you pick into the sorted cards in your hand.

Java Implementation

Here is my Java implementation of Insertion Sort algorithm:

/**
 * HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.
 * All sorting methods should have a signiture of 
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 1999 by Dr. Herong Yang
 */
public class HyArrays {
   public static void insertionSort(Object[] a, int fromIndex, 
      int toIndex) {
      Object d;
      for (int i=fromIndex+1; i<toIndex; i++) {
         d = a[i];
         int j = i;
         while (j>fromIndex && ((Comparable)a[j-1]).compareTo(d)>0) {
            a[j] = a[j-1];
            j--;
         }
         a[j] = d;
      }   
   }
}

The following diagram illustrates how this implementation works:

                             ----------24   4  53   ...            42
                            |               |   |                   |
        +-----------+---+---+---+---+---+---+---+-------------------+
        |           |   |    /   /   /                              
        5   ...    17  20  29  36  39                               
        |           |   |   |           |                           |
fromIndex             j-1   j           i                   toIndex-1

• Elements to be sorted are stored from "fromIndex" to "toIndex-1" inclusive.
• At any given time, elements from "fromIndex" to "i-1" are sorted.
• At any given time, elements from "i" to "toIndex-1" are not sorted.
• As shown in the diagram, element at location "i" needs to be inserted at location "j", and all elements from "j" to "i-1" need to be shifted to the right by one location.

Performance

Now let's see how it performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:

Array size: 1000
Average sorting time: 21 milliseconds
Number of tests: 1000
Performance: 21.0 O(N) nonaseconds
Performance: 2.1072099696478683 O(N*Log2(N)) nonaseconds
Performance: 0.021 O(N*N) nonaseconds

Array size: 2000
Average sorting time: 83 milliseconds
Number of tests: 1000
Performance: 41.5 O(N) nonaseconds
Performance: 3.784499031049363 O(N*Log2(N)) nonaseconds
Performance: 0.02075 O(N*N) nonaseconds

Array size: 3000
Average sorting time: 191 milliseconds
Number of tests: 1000
Performance: 63.666666666666664 O(N) nonaseconds
Performance: 5.511909130172683 O(N*Log2(N)) nonaseconds
Performance: 0.021222222222222222 O(N*N) nonaseconds

The results showed us that the performance of insertion method is O(N*N), because the last performance line gave me a constant, when I increased the array size.

(Continued on next part...)

Part:   1  2 

This site Web