WHAT IS INSERTION SORT ?

INSERTION SORT 

Insertion sort is a very simple sorting algorithm in which the sorted array (or list) is built one element at a time. We all are familiar with this technique of sorting, as we usually use it for ordering a deck of cards while playing bridge. The main idea behind insertion sort is that it inserts each item into its proper place in the final list. To save memory, most implementations of the insertion sort algorithm work by moving the current data element past the already sorted values and repeatedly interchanging it with the preceding value until it is in its correct place. Insertion sort is less efficient as compared to other more advanced algorithms such as quick sort, heap sort, and merge so

Technique 

  Insertion sort works as follows:

•  The array of values to be sorted is divided into two sets. One that stores sorted values and another that contains unsorted values. 
•  The sorting algorithm will proceed until there are elements in the unsorted set. 
•  Suppose there are n elements in the array. Initially, the element with index 0 (assuming LB = 0) is in the sorted set. Rest of the elements are in the unsorted set. 
•  The first element of the unsorted partition has array index 1 (if LB = 0). 
• During each iteration of the algorithm, the first element in the unsorted set is picked up and inserted into the correct position in the sorted set.

ALGORITHM:

  INSERTION-SORT (ARR, N)

Step 1: Repeat Steps 2 to 5 forK=1toN–1 

Step 2:  SET TEMP = ARR[K] 

 Step 3: SETJ=K-1

 Step 4: Repeat while TEMP <= ARR[J]

SET ARR[J + 1] = ARR[J] 

SETJ=J-1

[END OF INNER LOOP] 

Step 5:  SET ARR[J + 1] = TEMP

[END OF LOOP]

 Step 6: EXIT

Advantages of Insertion Sort

The advantages of this sorting algorithm are as follows: 

•  It is easy to implement and efficient to use on small sets of data. 
•  It can be efficiently implemented on data sets that are already substantially sorted. 
•  It performs better than algorithms like selection sort and bubble sort. Insertion sort algorithm     is simpler than shell sort, with only a small trade-off in efficiency. It is over twice as fast as       the bubble sort and almost 40 per cent faster than the selection sort. 
•  It requires less memory space (only O(1) of additional memory space). 
•  It is said to be online, as it can sort a list as and when it receives new elements.

let insertionSort= (A) =>{ let i,j,temp; for (i=1;i<A.length;i++){       temp=A[i];       for(j=i-1;j>=0 && temp<A[j];j--)           A[j+1]=A[j];     A[j+1]=temp; } } let A=[566,899,100,99,56,45,12,10,9,8,7,6,4,0,65,78,3,1,2,45] insertionSort(A); console.log(A) console.log(A.length)