The following are the procedures for Sorting a given data element by Insertion Sort algorithm :
First of all, the given data element set will be stored in an array.
Let the first element of the array remain in the same place.
Select the second element of the array and combine it with the first element of the array.
If an element is found to be larger than the selected element, then the selected is inserted at that place, otherwise no.
Element fix their positions after the insertion process.
This process is applied sequentially with the selection of all elements of the array.
In this way a sorted sequence of the given data element is obtained.
Ex :- 50,10,100,20,60,15
Take an array and insert all element into the array-
Choose the second element A2 i.e. 10 from the array and compare it with previous by array element and insert at proper.
Choose the next element as i.e. 100 from the array and insert at proper position.
Choose the next element as i.e. 20 from the array and insert at proper position.
Choose the next element as i.e. 60 from the array and insert at proper position.
Choose the next element as i.e. 15 from the array and insert at proper position.
finally sorted array.
Algorithm :-
Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.
Step 1 :- If it is the first element, it is already sorted. return 1;
Step 2 :- Pick next element.
Step 3 :- Compare with all elements in the sorted sub-list that is greater than the value to be sorted.
Step 4 :- Insert the value.
Step 5 :- Repeat until list is sorted.
Program :-
Output :-
[5, 9, 11, 12, 16]
Complexity Analysis of Insertion Sort :-
Time complexity of Insertion Sort-
The Worst-case time complexity of the Insertion Sort is 0(N^2).
The Average case time complexity of the Insertion Sort is 0(n^2).
The time complexity of the Best case is 0(N).