Insertion Sort in C++ Program Example & Algorithm

What is Insertion Sort?

Insertion sort is a very famous algorithm used to sort elements in ascending order. It works by comparing the elements and checking if they are already in ascending order.

It starts with the first element and the second. If this element is smaller than the first, it is placed at the first element’s position. After that, the third element is compared with the second, and the process continues until the entire array is sorted.

This algorithm is efficient for a small array of elements, but not for large arrays. 

For example, while playing cards we start sorting handful of cards in desired order starting with a random card & sort them till all are organised.  

How Insertion Sort  C++ Works

• 13,32,26,9,34,18,41,43           //list of values in the array.
• 13,32,26,9,34,18,41,43           //13,32 are in ascending order & moves to next  element further.
• 13,32,26,9,34,18,41,43           //26 after 13 is moved after comparing with 32.
• 13,26,32,9,34,18,41,43           //9 hold 1st position as it is smallest number after comparing in all sorted values in list 13,26,32. 
• 9,13,26,32,34,18,41,43          //Sorted Output

And So on sort out all values and arrange them in ascending order and produced the final result.

Insertion Sort C++ Algorithms

The algorithm for insertion sort is very efficient for small sets of data like small arrays. It can be considered adaptive as the algorithm might reduce the number of steps during execution. This can only happen if the algorithm is supplied a partially sorted array as the input.

The space complexity is less in this algorithm and is better considered better than Bubble or Selection sort algorithms. Some salient features of the algorithm are:

• Space Complexity: O(1)
• Best Case Time Complexity: O(n)
• Average Time Complexity: O(n2)
• Worst Case Time Complexity: O(n2)

Among all array taking the first value as starting one and comparing with & traverse till end of list.

1. Insertion Sort takes first value as random get it sorted and returns this.
2. Compare with next value and insert according.
3. Compare all elements in the list find greater / lesser and moves to its designated position.
4. Insert all values and repeat this step until all elements are sorted out.
5. Stop and exit.

C++ Insertion Sort Example 

#include <iostream>
using namespace std;
int main()
{
int st[16], i, j, k, temp;
cout<<"enter 5 elements only to sort n:-";
for (i = 0; i < 5; i++)
{
cin>>st[i];
}
for (i = 1; i < 5; i++)
{
for (j = i; j >= 1; j--)
{
if (st[j] < st[j-1])
{
temp = st[j];
st[j] = st[j-1];
st[j-1] = temp;
}
else
break;
}
}
cout<<"sorted array n "<<endl;
for (k = 0; k < 5; k++)
cout<<st[k]<<endl;
}

Output of the Program

enter 5 elements only to sort:-

• 56
• 10
• 5
• 3
• 1

Sorted Array 

• 1
• 3
• 5
• 10
• 56