Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
Insertion Sort - Implementation Improvements
This section provides a tutorial on how to improve the performance of the Insertion Sort implementation by using binary search method.
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.sort(). * All sorting methods should have a signature of * %Sort(Object[] a, int fromIndex, int toIndex) * where "fromIndex" is inclusive, and "toIndex" is exclusive. * Copyright (c) 2011 HerongYang.com. All Rights Reserved. */ public class HyArrays { public static void insertionSortImproved(HyObject[] a, int fromIndex, int toIndex) { HyObject d; for (int i=fromIndex+1; i<toIndex; i++) { d = a[i]; int jLeft = fromIndex; int jRight = i-1; if ((a[jRight]).compareTo(d)>0) { while (jRight-jLeft>=2) { int jMiddle = (jRight-jLeft)/2 + jLeft - 1; if ((a[jMiddle]).compareTo(d)>0) { jRight = jMiddle; } else { jLeft = jMiddle + 1; } } if (jRight-jLeft==1) { int jMiddle = jLeft; if ((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: 10000 Average sorting time: 55 milliseconds Number of tests: 1000 Performance: 5.5 O(N) microseconds Performance: 0.4139162440379741 O(N*Log2(N)) microseconds Performance: 5.5E-4 O(N*N) microseconds Array size: 20000 Average sorting time: 221 milliseconds Number of tests: 1000 Performance: 11.05 O(N) microseconds Performance: 0.7733918283388941 O(N*Log2(N)) microseconds Performance: 5.525E-4 O(N*N) microseconds Array size: 30000 Average sorting time: 500 milliseconds Number of tests: 1000 Performance: 16.666666666666668 O(N) microseconds Performance: 1.1206233445454983 O(N*Log2(N)) microseconds Performance: 5.555555555555556E-4 O(N*N) microseconds
It is still at the order of O(N*N). But I have reduced the performance by 78% from 0.641 to 0.500 seconds on the array size of 30,000.
Question: Can you do better than this? If you can, please let me know.
As a reference, results from an older computer are listed below:
Array size: 1000 Average sorting time: 9 milliseconds Number of tests: 1000 Performance: 9.0 O(N) microseconds Performance: 0.9030899869919435 O(N*Log2(N)) microseconds Performance: 0.0090 O(N*N) microseconds Array size: 2000 Average sorting time: 34 milliseconds Number of tests: 1000 Performance: 17.0 O(N) microseconds Performance: 1.5502767115141969 O(N*Log2(N)) microseconds Performance: 0.0085 O(N*N) microseconds Array size: 3000 Average sorting time: 76 milliseconds Number of tests: 1000 Performance: 25.333333333333332 O(N) microseconds Performance: 2.193220386874994 O(N*Log2(N)) microseconds Performance: 0.008444444444444444 O(N*N) microseconds
Table of Contents
Introduction of Sorting Algorithms
Java API for Sorting Algorithms
►Insertion Sort Algorithm and Java Implementation
Insertion Sort - Algorithm Introduction
Insertion Sort - Java Implementation
►Insertion Sort - Implementation Improvements
Selection Sort Algorithm and Java Implementation
Bubble Sort Algorithm and Java Implementation
Quicksort Algorithm and Java Implementation
Merge Sort Algorithm and Java Implementation
Heap Sort Algorithm and Java Implementation
Shell Sort Algorithm and Java Implementation
Sorting Algorithms Implementations in PHP
Sorting Algorithms Implementations in Perl
Sorting Algorithms Implementations in Python