Insertion Sort-
- Insertion sort is an in-place sorting algorithm.
- It uses no auxiliary data structures while sorting.
- It is inspired from the way in which we sort playing cards.
How Insertion Sort Works?
Consider the following elements are to be sorted in ascending order-
6, 2, 11, 7, 5
Insertion sort works as-
Firstly,
- It selects the second element (2).
- It checks whether it is smaller than any of the elements before it.
- Since 2 < 6, so it shifts 6 towards right and places 2 before it.
- The resulting list is 2, 6, 11, 7, 5.
Secondly,
- It selects the third element (11).
- It checks whether it is smaller than any of the elements before it.
- Since 11 > (2, 6), so no shifting takes place.
- The resulting list remains the same.
Thirdly,
- It selects the fourth element (7).
- It checks whether it is smaller than any of the elements before it.
- Since 7 < 11, so it shifts 11 towards right and places 7 before it.
- The resulting list is 2, 6, 7, 11, 5.
Fourthly,
- It selects the fifth element (5).
- It checks whether it is smaller than any of the elements before it.
- Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5 before them.
- The resulting list is 2, 5, 6, 7, 11.
As a result, sorted elements in ascending order are-
2, 5, 6, 7, 11
Insertion Sort Algorithm-
Let A be an array with n elements. The insertion sort algorithm used for sorting is as follows-
for (i = 1 ; i < n ; i++) { key = A [ i ]; j = i - 1; while(j > 0 && A [ j ] > key) { A [ j+1 ] = A [ j ]; j--; } A [ j+1 ] = key; }
Here,
- i = variable to traverse the array A
- key = variable to store the new number to be inserted into the sorted sub-array
- j = variable to traverse the sorted sub-array
Insertion Sort Example-
Consider the following elements are to be sorted in ascending order-
6, 2, 11, 7, 5
The above insertion sort algorithm works as illustrated below-
Step-01: For i = 1
Step-02: For i = 2
Step-03: For i = 3
2 | 5 | 11 | 7 | 6 | For j = 2; 11 > 7 so A[3] = 11 | |
2 | 5 | 11 | 11 | 6 | For j = 1; 5 < 7 so loop stops and A[2] = 7 | |
2 | 5 | 7 | 11 | 6 | After inner loop ends |
Working of inner loop when i = 3
Step-04: For i = 4
Loop gets terminated as ‘i’ becomes 5. The state of array after the loops are finished-
With each loop cycle,
- One element is placed at the correct location in the sorted sub-array until array A is completely sorted.
Time Complexity Analysis-
- Selection sort algorithm consists of two nested loops.
- Owing to the two nested loops, it has O(n^{2}) time complexity.
Time Complexity | |
Best Case | n |
Average Case | n^{2} |
Worst Case | n^{2} |
Space Complexity Analysis-
- Selection sort is an in-place algorithm.
- It performs all computation in the original array and no other array is used.
- Hence, the space complexity works out to be O(1).
Important Notes-
- Insertion sort is not a very efficient algorithm when data sets are large.
- This is indicated by the average and worst case complexities.
- Insertion sort is adaptive and number of comparisons are less if array is partially sorted.
To gain better understanding about Insertion Sort Algorithm,
Next Article- Merge Sort
Other Popular Sorting Algorithms-
Get more notes and other study material of Design and Analysis of Algorithms.
Watch video lectures by visiting our YouTube channel LearnVidFun.