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(elem);

System.out.print(" ");

}

System.out.println();

}

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();

is.doInsertionSort(s);

is.doInsertionSort(intArray);

printArray(s);

printArray(intArray);

}

}

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) .

Analysis

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