CPP Insertion Sort

#1

I am not clear with insertion sorting

#2

Think it this way
Let’s suppose that there are N elements in the array which needs to be sorted and starting N - 1 elements are already sorted
Then to sort the whole array what you need to do is correctly place the Nth element
Ex:- Let there be 5 elements :- 1 3 4 9 2
The starting 4 elements are already sorted. To sort the whole array you need to place the 5th element correctly.
So you back to search for its correct place.
While going backwards
You first see if 2 is greater than 9 – NO
Then if 2 lies between 4 and 9 – NO
Then if 2 lies between 3 and 4 – NO
Then if 2 lies between 1 and 3 – YES
STOP
Shift each element after and including 3, one unit to the right, to make space for element 2
place element 2 before 3

Now What if only 3 elements from the start were sorted:- 1 3 9 4 2
Then you will first place the 4th element correctly
So you back to search for its correct place.
While going backwards
You first see if 4 is greater than 9 – NO
Then if 4 lies between 3 and 9 – YES
STOP
Shift each element after and including 9, one unit to the right, to make space for element 4
place element 4 before 9
Now starting 4 elements are sorted and now we can sort the 5th element as above.

Similar could be done if only 2 starting elements were sorted OR only 1 starting element was sorted

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.