Insertion Sort in C++
In this tutorial, we are going to learn about one of the most common and simplest sorting techniques – insertion sort, and we are going to see how this technique is implemented in C++.
We will be covering the following sections today:
- What is Insertion Sort?
- Working of Insertion Sort
- Insertion Sort in C++
- Time Complexity Analysis of Insertion Sort
What is Insertion Sort?
The insertion sort is a sorting algorithm that places an unsorted element of an array at its suitable place with each iteration.
It works similar to how we sort the playing cards in our hands during a card game – the first card is always assumed to be sorted already. Then an unsorted card is selected, and if it is greater than the first card, we place it to its right, otherwise left. Then, we look at the next unsorted card and place it in its correct position based on its value.
Also Read: Classes and Objects in C++
Similarly, the insertion sort virtually splits an array into two parts – sorted and unsorted. Then, one by one, each element from the unsorted part is picked and placed at the correct position in the sorted part, until we get a final sorted array.
Let’s understand this approach in detail:
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Working of Insertion Sort
Let’s say we need to sort the following array:
Step 1:
- We assume that the first element of the above array to be sorted as we begin.
- Now, we will consider the second element and store it in a separate key.
- We then compare the first element to the key. If key < element 1, then the key is placed before element 1, as shown through the illustration below:
Step 2:
- Now that the first two elements of the array are sorted, let’s look at the third element.
- We store element 3 in the key and then compare the key to the elements before it.
- If key < element 2, then the key is placed before element 2.
- Then we compare the key with element 1, if key < element 1, we place the key at the beginning of the array.
- However, if key > element 2, it is the largest value, and hence, it is stored after element 2.
- This is shown through the illustration below:
Step 3:
- Let’s repeat the steps for the rest of the elements. The next element to be placed in the key is element 4, as illustrated below:
Step 4:
- Similarly, the next element to be placed in the key is element 5, as illustrated below:
Step 6:
- Lastly, we place our sixth element in the key, as illustrated below:
See how easy it is!
Now, let’s see how we implement this logic in C++:
//Insertion Sort in C++ #include <iostream>using namespace std; //Function to print an arrayvoid array(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl;} void InsertionSort(int arr[], int size) { for (int step = 1; step < size; step++) { int key = arr[step]; int j = step - 1; //Now we compare key with each element on its left until an element smaller than the key is found. //For descending order, we simply change key < arr[j] to key > arr[j]. while (key < arr[j] && j >= 0) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; }} //Driver codeint main() { int data[] = {9, 5, 3, 0, 1, 6}; int size = sizeof(data) / sizeof(data[0]); InsertionSort(data, size); cout << "The array sorted in ascending order using insertion sort:\n"; array(data, size); }
Output:
What have we done here?
As you can see from the code above, we begin sorting from the second element of the array (loop variable j = 1) and iteratively compare the current element (key) to all the previous elements.
The key is then placed in its correct position based on the order specified (key < arr[j] for ascending, and key < arr[j] for descending).
Time Complexity Analysis of Insertion Sort
The insertion sort algorithm works best with fewer passes if the array is already sorted partially. But as the array size grows larger, the performance of the algorithm reduces in efficiency.
However, as insertion sort uses a while loop for its execution, it is a more efficient algorithm than bubble sort or selection sort, which use for loop and present conditions.
But, even if a sorted array is passed to the insertion sort algorithms, the outer for loop will still get executed, thereby requiring n steps to sort even an already sorted array. So, the optimum time complexity of insertion sort is a linear function of n, where n is the size (number of elements) of the array.
The time complexities for insertion sort are as follows:
| Best Case Time Complexity | O(n) |
| Worst Case Time Complexity | O(n2) |
| Average Time Complexity | O(n2) |
| Space Complexity | O(1) |
Best Case Complexity
Let’s suppose we have an already sorted array. In this case, the outer for loop runs n times, whereas the inner loop does not run at all. So, the algorithm makes only n comparisons. This is the best-case complexity, i.e., linear complexity.
Worst Case Complexity
Let’s suppose we have an array in ascending order. Now, we want to sort this array in descending order. This is when the worst-case complexity occurs.
This happens because each element of the array has to be compared with each of the other elements. So, for every nth element, the algorithm has to make (n-1) comparisons.
Thus, the total number of comparisons: n*n-1 ~ n2
Average Complexity
The average complexity occurs when elements of the array are jumbled (neither in ascending nor descending order).
Space Complexity
The space complexity is given as O(1) because an extra variable key is used by the algorithm.
Also Read: OOPs concepts in C++
Endnotes
Insertion sort is the most efficient of all the three sorting techniques. This technique assumes that the first element is already sorted and then iteratively compares every element to the previous ones. Based on the order, it then places the current element in its correct position. In this tutorial, we focused on how insertion sort is implemented in C++. Hope this article proved to be useful for you.
FAQs
Can Insertion Sort handle large datasets efficiently?
Insertion Sort is not the most efficient algorithm for handling large datasets. Its time complexity of O(n^2) makes it less suitable for large arrays. Other sorting algorithms like Merge Sort or Quick Sort are more efficient for handling large datasets.
Is Insertion Sort stable?
Yes, Insertion Sort is a stable sorting algorithm. It maintains the relative order of elements with equal values. If two elements have the same value, the element that appears earlier in the original array will also appear earlier in the sorted array.
Can Insertion Sort be implemented recursively?
While Insertion Sort is typically implemented iteratively, it is possible to implement it recursively. However, the recursive implementation is not efficient and may lead to stack overflow errors for large arrays. Iterative implementation is generally preferred for Insertion Sort.
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
