the smallest, so it will be then placed at the second position. Then leaving and because they are at the correct position, we will search for the next smallest element from the rest of the elements and put it at third position and keep doing this until array is sorted. Finally we will get the sorted array end of the pass as shown above diagram. .
. Insertion sort Insertion sort is a simple sorting algorithm. It works by taking elements from the list one by one and inserting then in their correct position in to a new sorted list. This algorithm builds the final sorted array at the end.
This algorithm uses n- number of passes to get the final sorted list as per the pervious algorithm as we have discussed. Procedure for Insertion sort Step − If it is the first element, it is already sorted. Step − Pick next element 12th Computer Chapter - - Algorithmic Strategies Step − Compare with all elements in the sorted sub-list Step − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step − Insert the value Step − Repeat until list is sorted Assume is a sorted list of item inserted inserted inserted inserted inserted inserted inserted inserted At the end of the pass the insertion sort algorithm gives the sorted output in ascending order as shown below: Dynamic programming . .