Insertion sort is a simplistic sorting method that creates the final sorted array one item at a time.
Table of Content
- Working of Insertion Sort Algorithm
- Advantages of Insertion Sort Algorithm
- Insertion Sort Complexity
- Time Complexity
- Space Complexity
Working of Insertion Sort Algorithm
We used an unsorted array to demonstrate how the insertion sort algorithm functions.
Let the components of the array are –
At first, we contrasted the first two components of the insertion sort.
Here, 31 is greater than 12. Therefore, since the array’s components are already arranged in ascending order, we don’t need to modify anything. We can state that 11 is currently kept in a sorted sub-array.
It’s time to contrast the next two components.
25 in this array is less than 31. That means this is where we have to swap places. Element 31 is not at the accurate place. We must replace 31 with 25. Now we’ll validate it with every element in the sorted array using the insertion sort technique.
The array now only has one element, namely 12, hence it is empty. Therefore, 25 is more than 11. Therefore, even after swapping, the array will still be sorted.
Currently, two of the organised array’s components are 12 and 25. It’s time to think about the following two components, which are 31 and 8.
31 and 8 are both unorganised components. Therefore, we need to do a swap transaction.
The components 25 and 8 are clearly out of order after the switch.
So, swap them.
Additionally, the components 12 and 8 are not sorted.
Therefore, we must also perform swap operations on them.
The sorted array now contains three components with the values 8, 12, and 25. Go to items 31 and 32 in the following list.
These array elements are already sorted.
We’ll go on to the following two components, which are 32 and 17.
17 is less than 32 in size. In order to work on them, we must exchange them.
Both elements, 31, and 17, are unsorted after the swap. Therefore, we must switch them.
After exchanging, 25 and 17 are no longer sorted. We use swap operations once more.
Now, the array is fully sorted.
Advantages of Insertion Sort Algorithm
The implementation of insertion sort is very easy.
- The nature of this algorithm is quite adaptive, which means this is good for data sets that are already sorted.
Let’s now examine how the insertion sort algorithm functions.
Insertion Sort Complexity
1. Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
2. Space Complexity
| Space Complexity | O(1) |
|---|
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
