Insertion Sort

Part:   1  2 

(Continued from previous part...)

I also executed my SortTest.java with java.util.Arrays.sort():

Array size: 10000
Average sorting time: 17 milliseconds
Number of tests: 1000
Performance: 1.7 O(N) nonaseconds
Performance: 0.127937748157192 O(N*Log2(N)) nonaseconds
Performance: 1.7E-4 O(N*N) nonaseconds

Array size: 20000
Average sorting time: 45 milliseconds
Number of tests: 1000
Performance: 2.25 O(N) nonaseconds
Performance: 0.1574779740961549 O(N*Log2(N)) nonaseconds
Performance: 1.125E-4 O(N*N) nonaseconds

Array size: 30000
Average sorting time: 70 milliseconds
Number of tests: 1000
Performance: 2.3333333333333335 O(N) nonaseconds
Performance: 0.15688726823636978 O(N*Log2(N)) nonaseconds
Performance: 7.777777777777778E-5 O(N*N) nonaseconds

The results was very impressive. I had to increase the array size to 10000 to get the performance measurements. As you can see, the performance is at the order of O(N*Log2(N)).

Improvements

One area to improve this implementation is the inner loop, where we sequentially comparing each element with the selected element by the outer loop. Since we are doing this in the sorted section of the collection, we could replace this search by a binary search method.

Here is my improved implementation of insertion sort:

/**
 * 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 insertionSortImproved(Object[] a, int fromIndex, 
      int toIndex) {
      Object d;
      for (int i=fromIndex+1; i<toIndex; i++) {
         d = a[i];
         int jLeft = fromIndex;
         int jRight = i-1;
         if (((Comparable)a[jRight]).compareTo(d)>0) {
            while (jRight-jLeft>=2) {
               int jMiddle = (jRight-jLeft)/2 + jLeft - 1;
               if (((Comparable)a[jMiddle]).compareTo(d)>0) {
                  jRight = jMiddle;
               } else {
                  jLeft = jMiddle + 1;
               }
            }
            if (jRight-jLeft==1) {
               int jMiddle = jLeft;
               if (((Comparable)a[jMiddle]).compareTo(d)>0) {
                  jRight = jMiddle;
               } else {
                  jLeft = jMiddle + 1;
               }
            }
            int j = i;
            for (j=i; j>jLeft; j--) {
               a[j] = a[j-1];
            }
            a[j] = d;
         }
      }   
   }
}

Of course, it has more lines of code. But watch the improvement in performance:

Array size: 1000
Average sorting time: 9 milliseconds
Number of tests: 1000
Performance: 9.0 O(N) nonaseconds
Performance: 0.9030899869919435 O(N*Log2(N)) nonaseconds
Performance: 0.0090 O(N*N) nonaseconds

Array size: 2000
Average sorting time: 34 milliseconds
Number of tests: 1000
Performance: 17.0 O(N) nonaseconds
Performance: 1.5502767115141969 O(N*Log2(N)) nonaseconds
Performance: 0.0085 O(N*N) nonaseconds

Array size: 3000
Average sorting time: 76 milliseconds
Number of tests: 1000
Performance: 25.333333333333332 O(N) nonaseconds
Performance: 2.193220386874994 O(N*Log2(N)) nonaseconds
Performance: 0.008444444444444444 O(N*N) nonaseconds

It is still at the order of O(N*N). But I have reduced the performance factor by 60% from 0.021 to 0.0084.

Question: Can you do better than this? If you do, please let me know.

Part:   1  2 

This site Web