Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
Insertion Sort - Java Implementation
This section provides a tutorial on how to implement the Insertion Sort algorithm in Java. An implementation diagram is also provided.
Here is my Java implementation of Insertion Sort algorithm in the HyArrays.java class:
/* 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 insertionSort(HyObject[] a, int fromIndex, int toIndex) { HyObject d; for (int i=fromIndex+1; i<toIndex; i++) { d = a[i]; int j = i; while (j>fromIndex && (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
Note that:
In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old implementation:
/* HyArraysOld.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) 2008 HerongYang.com. All Rights Reserved. */ 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; } } }
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