Insertion Sort

Insertion Sort is a simple sorting algorithm that build final sorted element in the array. The insertion sort give more efficient way and give more advantage than other sort like quick sort, merge sort and heap sort. 

It's specialties are :

• Simple
• More efficient ( Time Complexity O(n²) )
• Only required constant amount of memory requirement. ( O(1) )

Algorithm
------------------------------------------------------------------------------------------------------------
Insertion_Sort(array){
     for i=1 to n-1{
          element = array[i];
          j=i;
          while(j>0 and array[j-1] > element ){
                 array[j] = array[j-1];
                 j=j-1;
          } 
          array[j] = element;
     }
}

Implementation is below : 
 

	public class Insertion_Sorting {
	private int[] A;
	public void read(int[] A){
	this.A = A;
	}
	public int[] sort(){
	for (int i = 1; i <= A.length-1; i++) {
	int element = A[i];
	int j = i;
	while (j>0 && (A[j-1] > element)) {
	A[j] = A[j-1];
	j--;
	}
	A[j] = element;
	}
	return A;
	}
	public void print(){
	for (int i = 0; i < A.length; i++) {
	System.out.print(A[i] + " ");
	}
	}
	public static void main(String[] args){
	int[] A = {23,42,4,16,8,15};
	Insertion_Sorting I = new Insertion_Sorting();
	I.read(A);
	I.sort();
	I.print();
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub