Rearranging data in a logical order is known as sorting i.e. arranging of data in ascending or descending order. In this article, we will learn about insertion sort in C++.
Insertion sorting is done in the same way as we sort our cards in while we play games of cards
Time Complexity
O(n2)
Best Case
Ω(n)
Worst Case
O(n2)
Aux. Space Complexity
O(1)
Best case when
Array is already sorted
Worst case when
Array is reverse sorted
Insertion Sort in C++
If there are n element and it requires (n-1) pass to sort them then, at each pass we insert current element in the appropriate position so that the element are in order. Some characteristics of insertion sort in C++.
A sub-list is maintained which is always in sorted order.
It is better then Selection Sort and Bubble Sort algorithms.
It is efficient for smaller data sets but inefficient for larger data sets.
Its space complexity is less.
It does not change the relative order of elements which are equal.
Execution of insertion sort in C++
It’s almost similar to how we play cards.
At any given time, one part of the array will be sorted and one part will be unsorted.
We will pick the leftmost item from the unsorted part
Insert this item at the correct position in the sorted array
You can check the implementation of the same below
// C++ Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Compelexity : O(1)
// Best Case : When already Sorted, Worst Case : When reverse Sorted
#include<iostream>
using namespace std;
//Function to print array.
void display(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << "\t";
cout << "\n";
}
//Main function to run the program.
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4,7};
int size = sizeof(array)/sizeof(array[0]);
cout << "Before Insertion sort: \n";
display(array, size);
int i, key, j;
for (i = 1; i < size; i++) { key = array[i]; j = i - 1; /* Here the elements in b/w arrary[i-1 & 0] which are greater than key are moved ahead by 1 position each*/ while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1; // moving backwards
}
// placing key item now
array[j + 1] = key;
}
cout << "After Insertion sort: \n";
display(array, size);
return 0;
}
Anyone can write it is moderately easy to understand
Only O(1) space requirements
For a smaller number of items in an array it’s quicker than merge sort
Cons
Not so good average time complexity of O(n2)
If there are large elements then it gives bad performance because of O(n^2) time complexity
Shifting items because of insertion can be costly
Other information
Best Case: If already sorted data set
Worst Case: Sorted data set but in the opposite order
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Login/Signup to comment