Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Working of Insertion Sort algorithm:
Consider an example: arr[]: {12, 11, 13, 5, 6}
First Pass:
- Initially, the first two elements of the array are compared in insertion sort.
- Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its correct position. Thus, swap 11 and 12.
- So, for now 11 is stored in a sorted sub-array.
Second Pass:
- Now, move to the next two elements and compare them
- Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no swapping will occur. 12 also stored in a sorted sub-array along with 11
Third Pass:
- Now, two elements are present in the sorted sub-array which are 11 and 12
- Moving forward to the next two elements which are 13 and 5
- Both 5 and 13 are not present at their correct place so swap them
- After swapping, elements 12 and 5 are not sorted, thus swap again
- Here, again 11 and 5 are not sorted, hence swap again
- here, it is at its correct position
Fourth Pass:
- Now, the elements which are present in the sorted sub-array are 5, 11 and 12
- Moving to the next two elements 13 and 6
- Clearly, they are not sorted, thus perform swap between both
- Now, 6 is smaller than 12, hence, swap again
- Here, also swapping makes 11 and 6 unsorted hence, swap again
- Finally, the array is completely sorted.
Illustrations:
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials
Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
When we have a large amount of data, it can be difficult to deal with it, especially when it is arranged randomly. When this happens, sorting that data becomes crucial. It is necessary to sort data in order to make searching easier.
Contact Us