Sunday, 15 March 2015

Insertion Sort in java


Insertion sort takes the input array and sorts it, all the elements in the array before the loop invariant (loop variable) are sorted. Hence we start our loop from index 1 and iterate.(Assuming that first element is sorted) While looping current item is compared with sorted array and its actual index identified, after loop completion it is inserted at its actual location.
Following program implements Insertion sort in java.
/**
 * @author vikky.agrawal
 * 
 */
public class InsertionSort {

	
	int[] arr;
	
	InsertionSort(){
		arr=new int[] { 5, 3, 1, 2, 9, 8 };
	}
	
	/**
	 * @param args
	 */
	
	public static void main(String[] args) {

		InsertionSort obj = new InsertionSort();
		obj.operate();
	}
	
	public void operate(){

		System.out.println("Array before sortings: ");
		printArray();
		sort();

		System.out.println("Sorted array : ");
		printArray();
	}
	

	/**
	 * Insertion Sort algo: 
	 * 1 for j=1 to Arr.length 
	 * 2 key= Arr[j]; 
	 * 3 //Insert Arr[j] into the sorted sequence Arr[0...j-1].
	 * 4 i=j-1; //initialization for looping 
	 * 5 while (i>=0 and Arr[i] >key) 
	 * 6   Arr[i+1]=Arr[i] 
	 * 7   i=i-1; 
	 * 8 Arr[i+1] = key
	 */

	public int[] sort() {

		int length = arr.length;
		int i = 0;
		int key = 0;
		for (int j = 1; j < length; j++) {
			i = j - 1;
			key = arr[j];
			while (i >= 0 && arr[i] > key) {
				arr[i + 1] = arr[i];
				i--;
			}
			arr[i + 1] = key;
		}

		return arr;
	}

	public void printArray(){
		for (int a : arr) {
			System.out.print(a + " ");
		}
		System.out.println();
	}
}
Complexity analysis of Insertion sort :
Outer loop runs for n-1 times.In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 = n*(n-1)/2 = n^2.
Hence to sum up the overall complexity worst case time required in insertion sort will be equal to O(n^2).

When to use insertion sort / Characteristics of Insertion sort
1. Insertion sort should be used when data is nearly sorted, in such cases inner while loop won't get executed and performance of insertion sort remains better than its worst case.
2. Insertion sort could be used when data size is smaller, as it requires little/no overhead.
3. It's stable sort (i.e. does not change the relative order of elements with equal values after sorting)
4. In-place sorting- requires constant amount of extra space.