Sunday, December 28, 2008

Insertion sort in Java using generics

Insertion sort
It looks at the next item of the input and inserts it into its correct position in the "already sorted" previous items of the input. Here is the code for it using Java Generics.

public class MyInsertionSort {

public <T extends Comparable<T>> void doInsertionSort(T[] input) {

if (input == null) {
throw new RuntimeException("Input array cannot be null");
int length = input.length;
//Already sorted
if (length == 1) return;
int i,j;
T temp;
for (i = 1; i < length; i++) {
//Store the current element
temp = input[i];
//Compare the current element with
//the partially sorted group
//to see if its in the correct position
for (j = i; (j > 0 && (temp.compareTo(input[j-1]) < 0)); j--){
//The current element is not in
// its correct position in the
//partially sorted list. Move
//the larger item one place
//to right and make space
// for the current element
input[j] = input[j-1];
//Found the correct position
//for the current element
//in the partially sorted group.
//So move it to its correct place.
input[j] = temp;


Test it.

public class MyMain {

public static <T> void printArray(T[] input) {
for(T elem: input) {
System.out.print(" ");

public static void main(String[] args) {

String[] s = {"Hello", "World", "Hello"};
Integer[] intArray = {1,4,9,0,8,7,9,6};

//Test insertionsort
MyInsertionSort is = new MyInsertionSort();



Running it produces the following output:
Hello Hello World
0 1 4 6 7 8 9 9

Efficiency of Insertion sort
In the first pass we will have max of 1 comparision,in the second one we will have a max of 2 comparisions and so on. So this is
1+2+3+....(n-1) and it sums up to roughly n(n-1)/2 i.e. approximately n². So the running time for random data it is O(n²) but for already sorted data it will never enter the second for loop, so it will run in O(n) .

The insertion sort is not a good sort for large inputs of data. More information on Insertion sort can be found here.

No comments:

Post a Comment