Insertion Sort

Insertion-sort

/*

  InsertionSort(A, n){
	for i <- 1 to n-1 
		value = A[i-1] 
		j = i-1;
		while( j > -1 & A[j] > value)
			A[j+1] = A[j]
			j--
		A[j+1] = value
	return A
	
  }
  
  Time Complexity = n * (n-1)/2 = O(n^2)
  
*/
var arr = [34,56,1,2,45,96,15,10];

function InsertionSort(arr){
	for(var i = 1; i <  arr.length; i++){ 
		var key = arr[i]; 
		var j = i - 1;  
		while(j > -1 && arr[j] > key){
			arr[ j + 1 ] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
	return arr;
}

TC: 
1. Assignments & Comparisons have constant time
2. While loop calculate , BC, AC, WC
    BC: 1,2,3,4,5
        O(n)
    WC: 5,4,3,2,1
        C2 * (n times) * (n-1) times   
        O(n2)
    AC: O(n2)