Insertion Sort - Your Sorting 101 Guide
Updated: Jun 3, 2022
Algorithm
In our last article we discussed the bubble sort sorting algorithm. This is another article in the series sorting algorithms. In this article we will discuss insertion sort.
Insertion sort is an in-place sorting algorithm. Insertion sort works by picking each unsorted element and placing it in its correct sorted position in the array. During its execution insertion sort divides the array into two portions, sorted portion and unsorted portion. Sorted elements will be on the left side of the array and unsorted elements will be on the right side. In each iteration one element is picked from unsorted portion and moved to its correct position in the sorted portion on the left.
For a given input array arr that needs to be sorted in ascending order, insertion sort does the following steps:
We assume that the first element is already sorted and start from the second element in the array.
We compare the second element to the element before it. If the current element is less than the element before it, we swap the two elements.
Next we move on to the third element and compare to all elements before it and swap if it is less than those elements.
We need to do the above steps for all the elements in the array.
To implement this algorithm we need to run two loops, an inner loop and an outer loop. Let i and j be the indexes of inner and outer loops respectively.
i points to the last sorted element in the sorted portion of the array. j points to the first unsorted element in the unsorted portion in the array.
To begin with we assume that the first element in the given array is sorted, so i points to the first element in the given array and j points to the second element.
We fix the outer loop and iterate through the inner loop. At the start of the inner loop we assign i to j, i.e j=i.
In each iteration of the inner loop check if arr[j] < arr[j-1]. As long as arr[j] < arr[j-1] we swap arr[j] and arr[j-1] decrement j. Else we break the inner loop and move on to the next iteration of the outer loop.
We repeat these steps until all the elements in the given array are processed.
Simulation
Consider we are given the below input array:
Below is a simulation of how insertion sort sorts the given array in each iteration. Element marked in green is the element under consideration for the current iteration that needs to be moved to its correct position in the sorted portion. Elements marked in grey are the elements that are already sorted.
Iteration 1
To start with we assume that the first element is already sorted. We start the iteration with the second element 19 (since we assumed the first element is already sorted). We compare 19 with every element on its left until it reaches the correct sorted position or there are no more elements to compare with.
First we compare 19 with the element before it, 17. Since 19 > 17, so there is no need to swap.
Since there are no more elements to compare we mark 17 and 19 as sorted as shown below:
Iteration 2
After the first iteration 1st two elements of the given array are sorted. In the second iteration we process the next unsorted element 4.
Compare 4 with all elements on its left starting from 19 until it moves to its correct sorted position.
Compare 4 with 19. 4 < 19, so swap.
Next compare 4 with 17. 4<17, so swap.
There are no more elements to compare with, therefore we mark 4, 17, 19 as sorted.
Iteration 3
Next unsorted element is 9. As earlier we compare it with 19, 17 and 4 and move it to its correct position in the array.
Now 9 is in its correct position in the array, we mark 4, 9, 17, 19 as sorted.
Iteration 4
Finally we compare 7 with elements before it 19, 17, 9, 4.
Mark 4, 7, 9, 17, 19 as sorted.
Now all the elements in the array are sorted, so we stop our algorithm.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Implementation
Code
Language: Go
Language: Python
Language: Java
Complexity Analysis
Time Complexity: O(n^2)
The worst case time complexity of the algorithm is O(n^2) since it uses two loops to arrive at the result. The worst case occurs when the array is sorted in descending order, in this case we end up making maximum number of comparisons to sort the array.
Space Complexity: O(1)
No extra space is used.
Now you know how insertion sort works. Don't stop here, you can explore more sorting algorithms from code recipe here.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe here.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now
Commentaires