INSERTION SORT
Insertion sort is based on the idea of consuming one element from unsorted array and inserting it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.
EXAMPLE:
To understand the insertion sort, lets consider an unsorted array [23, 1, 10, 5, 2] and discuss each step taken to sort the array in ascending order. In every pass, one element is taken from the unsorted array and inserted it at the correct position in the sorted array.
Steps:-
- First Pass: The whole array is unsorted array and (23) is taken to be inserted into the sorted array. As (23) is the first element of sorted array and has no elements to be compared with, it remains at its position.
- Second Pass: (1) is the taken from unsorted array to insert into sorted array. It is compared with all elements of sorted array and found that (23) is the only number which is greater than (1). (1) is inserted into the sorted array and position of (23) is shifted by one place in the array. This resulted into increasing the length of sorted array by one and decreasing the length of unsorted array by one.
- Third Pass: (10) is taken from the unsorted array and compared with all elements of sorted array. (23) is the only number in the sorted array which is greater than (10). (10) is inserted into the sorted array and position of (23) is shifted by one place in the array.
- Fourth Pass: (5) is compared with all elements of sorted array and it is found that (10) and (23) are the numbers which need to be shifted by one place to insert (5) into the sorted array.
- Fifth Pass: To insert (2) into the sorted array, (5), (10) and (23) are shifted by one place.