Insertion Sort in C++

Introduction to Insertion Sort in C++

Insertion Sort is a type of sorting algorithm where the elements are sorted using a sub-list which is maintained to be sorted, for example– the lower part of the array is always sorted. As we move forward the next element needs to search its right place in the sorted sub-list to be inserted in the list, thus known as insertion Sort. It is an in-place sorting algorithm since it does not uses much extra space for the comparisons of an element to sort them. Since all the elements are compared to each other element in the list thus its complexity is O(n2), where n is the number of elements in the list.

Logic behind Insertion Sort in C++

The idea behind the insertion sort is about selecting one element from the input array and placing it at the correct place such that sub-array of elements present before that element is sorted.

The sorted sub-array grows gradually with each iteration, where the current element is compared to the largest element in the sorted sub-array present before that element. In case new element is larger than is left at that position otherwise the correct position for that element is found by comparing to the next larger value in sorted array and element is inserted at the position where all the elements left to that position is smaller than it and elements present at the right is larger than that

Algorithm

Lets understand with pseudocode how this procedure works:-

InsertionSort(A,n)
1. For i in range(0,n): Repeat Steps 2 and 3
2. If i=0: return 1
Else for j in range(0,i) :compare A[i] and A[j] Shift the elements greater than A[i] towards right.
3. Insert the value at the right position.

Since sorting using insertion sort requires the array to be searched sequentially and then the new item is inserted to the sorted sub-array, the complexity of the algorithm in the average and worst case is of O(n2). Thus the above algorithm is not suitable for a large set of elements.

How to implement Insertion Sort in C++ using various methods?

Now let us implement the insertion sort for sorting various students whose heights(in cms) are in C++:

Example 1 – Implementation using Loops

#include <bits/stdc++.h>
using namespace std;
void iSort(int myarr[], int nElements)
{
int x, key, y;
for (x = 1; x < nElements; x++)
{
key = myarr[x];
y = x - 1;
while (y >= 0 && myarr[y] > key)
{
myarr[y + 1] = myarr[y];
y = y - 1;
}
myarr[y + 1] = key;
}
}
void printArray(int myarr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << myarr[i] << " ";
cout << endl;
}
int main()
{
int myarr[] = { 141,182,194,162,171,191,135};
int n = sizeof(myarr) / sizeof(myarr[0]);
iSort(myarr, n);
printArray(myarr, n);
return 0;
}

Explanation

myarr is the array that holds the elements in the list and sizeOf is an inbuilt method of C++ used to find the amount of memory being used by element. Thus the memory used by array/ memory used by one element gives the number of elements array holds. Here printArray method is used to print all the elements of the array, and iSort method is used to sort the array of elements passed as an argument along with the number of elements to be sorted. Here key variable is used to store the current element that needs to be placed at its correct position.

Output

Example 2- Using Standard Template Library(STL)

#include <bits/stdc++.h>
void iSort(std::vector<int> &myvec)
{
for (auto it = myvec.begin(); it != myvec.end(); it++)
{
auto const insertion_point =
std::upper_bound(myvec.begin(), it, *it);
std::rotate(insertion_point, it, it+1);
}
}
void print(std::vector<int> myvec)
{
for( int i : myvec)
std::cout << i << " ";
std::cout << '\n';
}
int main()
{
std::vector<int> myarr = {141,182,194,162,171,191,135};
iSort(myarr);
print(myarr);
}

Output

Example 3: Implementation of Insertion Sort using Recursion

Idea – The idea behind this implementation is that we keep the processed elements in every run thus we can use recursion to process them.

1. Base condition- Return in case size of the array is <=1

2. Sort the sub-array of size n-1 elements recursively.

3. Insert the next element in the correct position to maintain the sorted order.

#include <iostream>
using namespace std;
void iSort(int arr[], int n)
{ if (n <= 1)
iSort( arr, n-1 );
int end = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > end)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = end;
}
void printArray(int myarr[], int num)
{
for (int i=0; i < num; i++)
cout << myarr[i] <<" ";
}
int main()
{
int myarr[] = {141,182,194,162,171,191,135};
int n = sizeof(myarr)/sizeof(myarr[0]);
iSort(myarr,n);
printArray(myarr,n);
}

Output

Conclusion

Insertion sort is a type of sorting where elements are gradually inserted in a growing list of sorted elements and are compared to the elements in the list in descending order to place the new element in its correct place. This algorithm runs with time complexity of O(n2) in the worst and average case thus is suitable in case of a smaller set of elements.

Recommended Articles

This is a guide to Insertion Sort in C++. Here we discuss the introduction along with different examples and its code implementation. you may also have a look at the following articles to learn more –

1. C++ Struct Constructor
2. Recursion in C++
3. Python Sort List
4. Quick Sort in Python