Insertion Sort

This chapter helps you to understand:

• Basic Idea
• Java Implementation
• Performance
• Improvements

Basic Idea

The basic idea of Selection Sort:

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

2. Assuming the sorting order is from low to high, find the element with the lowest comparable order from the un-sorted section.

3. Place the found element to the end of the sorted section.

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

The idea of selection sort comes from our daily life experiences. For example, at the end of card game, if you want to sort all the cards by rank and suit, you would put all the cards on the table, face up, find the lowest rank card, and it to the sorted piles, one pile per suit.

Java Implementation

Here is my Java implementation of Selection 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 selectionSort(Object[] a, int fromIndex, 
      int toIndex) {
      Object d;
      for (int i=fromIndex; i<toIndex; i++) {
         int k = i;
         for (int j=i+1; j<toIndex; j++) {
            if (((Comparable)a[k]).compareTo(a[j])>0) {
               k = j;
            }
         }
         d = a[i];
         a[i] = a[k];
         a[k] = d;
      }   
   }
}

The following diagram illustrates how this implementation works:

                                -----------29
                                |  36  39      67   ...            42
                                |   |   |       |                   |
        +-----------+---+---+---+---+---+---+---+-------------------+
        |           |   |   |               |                      
        4   ...    17  20  24  53-----------                            
        |                   |   |           |                       |
fromIndex                 i-1   i           k              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, the element with the lowerest comparable order is located at "k", which will be placed at the end of the sorted section by swapping it with the element at location "i".

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: 38 milliseconds
Number of tests: 1000
Performance: 38.0 O(N) nonaseconds
Performance: 3.813046611743762 O(N*Log2(N)) nonaseconds
Performance: 0.038 O(N*N) nonaseconds

Array size: 2000
Average sorting time: 153 milliseconds
Number of tests: 1000
Performance: 76.5 O(N) nonaseconds
Performance: 6.976245201813886 O(N*Log2(N)) nonaseconds
Performance: 0.03825 O(N*N) nonaseconds

Array size: 3000
Average sorting time: 347 milliseconds
Number of tests: 1000
Performance: 115.66666666666667 O(N) nonaseconds
Performance: 10.01378255586346 O(N*Log2(N)) nonaseconds
Performance: 0.03855555555555556 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.

Comparing with the Insertion Sort implementation, the Selection Sort implementation is much slower, the execution time is doubled.

Improvements

I don't see any way to improve this implementation. Do you?

This site Web