Insertion Sort Algorithm

The insertion sort algorithm is a simple and efficient sorting algorithm. In this algorithm, we “insert” each element into it’s sorted position. We consider two subarrays here: the unsorted and sorted subarray. Initially, the unsorted subarray contains the entire integer array, except the first element and the sorted subarray contains only the first element of the integer array. On running a loop through the unsorted subarray we remove elements from the unsorted subarray and “insert” it into its sorted position in the sorted subarray.

Logic:
1. So we need to insert elements into their sorted position in the sorted subarray, so we start running a loop “i” from the second element (i.e. element indexed 1) of the integer array
2. Store the i th element in a variable- temp
3. Consider a variable “j” which is initially set to i-1 (i.e. the rightmost element of sorted subarray)
4. Run a while loop on the sorted subarray, starting from j and decrement it till j>=0. If the value in temp is lesser than the value in the while loop element then shift that while loop element to the right
5. On exiting the while loop assign temp to its correct position

You guys could refer to this super helpful video too! (LINK)

Code:

View on/ Download from Github: (LINK)

public class insertion_sort {
	public static void main (String [] args){
		int [] array= {4,2,8,6,1,0};
		int length=array.length;
		
		for(int i=1; i<length; i++){
			int temp=array[i];
			int j=i-1;
			while(j>=0 && array[j]>temp){
				array[j+1]= array[j];
				j--;
			}
			
			array[j+1]= temp;
		}
		
		
		//print array
		for(int i=0; i<length; i++){
			System.out.println(array[i]);
		}
	}

}

HAPPY LEARNING!!