Sorting and Searching algorithms like insertion sort, selection sort, merge sort are very important to learn as a part of the preparation of your placements and also for internships because these form the base of any programmer. As a programmer, you have to deal with large amounts of data. Hence, we use sorting algorithms and one of them is an insertion sort. Now, the Insertion sort algorithm is a comparison-based sorting algorithm in which the sorted array is built by inserting one element at its correct position at a time.
Additionally, Insertion sort requires two arrays, one ordered, and one unordered. Firstly, we consider our sorted array with only one element that is a[0]. After that, on each repetition, we set a key from the unordered list and compare it with the elements present in the ordered list. Then we insert that key into a sorted position in the ordered list until there are no elements left in the unordered list. While understanding insertion sort one thing you need to keep in mind is “Insert an element from unsorted array to its correct position in the sorted array”. In this section, we’re going to cover everything from working of insertion sort to implementation of insertion sort in python. Basically, you’re going to learn everything about insertion sort that you need to know at some specific point.
What you’ll learn?
- Working of Insertion sort algorithm with example
- Stepwise algorithm of insertion sort
- Pseudocode of insertion sort algorithm
- Implementation of the Insertion sort algorithm in Python
- Time complexity of insertion sort
- Space complexity of insertion sort
- Features of Insertion sort algorithm in python
- Why is insertion sort a stable sort?
- Is Insertion sort an in-place sorting algorithm?
Working of Insertion Sort with example
Let’s see now how insertion sort works with the help of an example. So, we have an array of 8 elements.
Input Array : 6 5 3 1 8 7 2 4
Now here first we will start with the second element because as we mentioned earlier that we consider the sorted array as having the first element only. One element is always sorted. So, we set the key equal to 5, and then we will see where we can place this key in the sorted array. As we can see 5 is smaller than 6 so we shift the 6 to one position ahead and place 5 before 6. Now our sorted array will become 5 6. After that, we will update the key to 3. Now, we will compare this key = 3 with the elements of the sorted array and place it to its correct position. As we can see 3 will be placed before 5. Now we have our sorted array as 3 5 6.
In the same, way we will go further. We will update the key to 1, then compare it with every element of the sorted array, afterward finds its correct position and place it. In the end, we will have our final sorted array.
Algorithm of Insertion sort
- Start by making the second element i.e. element at index 1, the
key. - We compare the
keyelement with the element(s) before it (elements of the sorted array), in this case, the element at index0:- If the
key< a[0] , we insert thekeyelement before a[0]. - If the
key> a[0], then we insert it after a[0].
- If the
- After that, we make the key equal to the third element of the array. Then we will compare it with elements to its left and insert it in the right position.
- And we go on repeating this until the whole array is sorted.
Pseudocode of insertion sort
Step1: Start loop from i = 1 to n-1
Step2: Set key = a[i]
Step3: Compare key with all the elements of sorted array using another loop
Step4: if the key is smaller than any element of the sorted array shift all the elements of the sorted array
Step5: End inner loop
Step5: Place key at its correct position
Step7: End outer loop
Implementation of the Insertion sort algorithm in Python
# Code by COPYASSIGNMENT.COM
# Insertion sort definition
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Shifting elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# Driver code to test above
arr = [15, 2, 56, 17,11]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i])Output:
C++ code
//Code By COPYASSIGNMENT
//Insert an element from an unsorted array to its correct position of sorted array.
#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
int key;
for (int i = 1; i < n; i++)
{
key = a[i];
int j;
for (j = i - 1; j >= 0; j--)
{
//Comparing key with elements of sorted array
if (a[j] > key)
{
a[j + 1] = a[j];
}
else
break;
}
//Setting key at right position
a[j + 1] = key;
}
}
int main()
{
int n;
//Taking size of array
cout << "Enter size of array : ";
cin >> n;
int arr[n];
//Taking array elements
cout << "Enter " << n << " elements : ";
for (int i = 0; i < n; i++)
cin >> arr[i];
insertion_sort(arr, n);
//Printing Sorted Array
cout << "Final Array : ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}Output:
Insertion sort time complexity
First, let’s see What is time complexity? Time complexity is defined as the order of growth of runtime of an algorithm in terms of input size. Now, in insertion sort when we have an array of n size, the algorithm performs n-1 passes. And the total no. of comparisons would be 1 + 2 + 3…(n-1) = n(n-1)/2 = O(n2)
- Best case complexity: The best case of insertion sort will be when we have a sorted array. Suppose we have an array as 1 2 3 4 5. In this case, we will compare 2 with 1, no swapping will take place. Then we compare 3 with 2, again no swapping will be done. Similarly in the end, total no. of comparisons will be 1 + 1 + 1 … = n-1. Therefore, the best-case time complexity of insertion sort is O(n).
- Worst case complexity: As discussed earlier, in the worst case our insertion sort algorithm will perform n(n-1)/2 comparisons which shows that the worst case time complexity of insertion sort is O(n2).
- Average case complexity: In most cases, the average case complexity is equal to the worst case complexity. So the average-case complexity of insertion is also O(n2).
Space complexity
Insertion sort is a stable sorting algorithm and therefore its space complexity is O(1). It doesn’t require any other extra space like stack to sort an array.
Features of Insertion sort
- It is efficient for the mostly sorted array.
- It is an adaptive sorting algorithm. That means it reduces its total number of comparisons/steps if a partially sorted array is provided as the input, making it efficient (as discussed in the time complexity section).
- Its space complexity is O(1).
- It is efficient for smaller size array.
- It uses an incremental approach as an algorithm paradigm.
- Insertion sort is an in-place sorting algorithm.
- Insertion sort algorithm is better than bubble sort and selection sort.
- It is a stable sort.
Why insertion sort is a stable sort?
First, let’s see what is a stable sort? A sorting algorithm that doesn’t affect the relative order of elements that are equal is called a stable sort.
Let us understand this with an example –
Input – 4A 5 3 2 4B 1
Output – 1 2 3 4A 4B 5
Note: Subscripts are for better understanding.
So, Yes, insertion sort is a stable sorting technique, as it does not change the relative order of elements that are equal.
Is Insertion Sort an in-place sorting algorithm?
Yes, It is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. All the swapping operations are done within the space of a single input array given initially.
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies!
Happy Coding!
You may also read
Introduction to Searching Algorithms: Linear Search Algorithm
Bubble Sort Algorithm In Data Structures & Algorithms using Python
Merge Sort Algorithm in Python
Sorting Algorithms and Searching Algorithms in Python
Shutdown Computer with Voice in Python
