Insertion Sort

• We divide an Array in Sorted and Unsorted Parts.
• We compare the first element of unsorted array with elementts of sorted array and put it in its right place.
• Scans array from A[1] to A[n] inserting each element A[k] into its proper position.
• Eccentricity of a node is the longest geodesic distance between that node and any other node. 
• Insert an element from unsorted array to its correct position in sorted array in each iteration.
• 12,45, 23, 51, 19, 8
• 12,23,45,51,19,8
• 12, 23, 45, 51, 19, 8
• 12, 19,23,45,51,8
• 8, 12, 19, 23, 45, 51
• Another Example
• 7,|8,3,1,2
• Here 7 is sorted array and remeining is unsorted I have added | for difference.
• 7,8|3,1,2
• compare 8 with 7 and plced in correct position.
• 3,7,8|1,2
• 1,3,7,8|,2
• 1,2,3,7,8|
• Key Terms
• Zero
• Variable
• FIFO
• LIFO
• Back
• Queue Linked List
• Node
• IsEmpty
• FrontOfStack