C++ Program for Insertion Sort

In this article, you will learn and get code to sort an array using the insertion sort technique in C++. The following programs are listed in insertion order:

Before going through these programs, if you're not aware of the steps and logic used behind insertion sort, then refer to the insertion sort algorithm and example to get all the things you need.

Insertion Sort in C++

To sort an array using the insertion sort technique in C++ programming, you have to ask the user to enter the size of the array and then enter elements of that size in random order. After receiving the inputs, sort the given array in ascending order using insertion sort as shown in the program given below:

The question is, "Write a program in C++ to implement insertion sort." Here is the answer:

#include<iostream>
using namespace std;
int main()
{
    int arr[50], tot, i, j, k, elem, index;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    for(i=1; i<tot; i++)
    {
        elem = arr[i];
        if(elem<arr[i-1])
        {
            for(j=0; j<=i; j++)
            {
                if(elem<arr[j])
                {
                    index = j;
                    for(k=i; k>j; k--)
                        arr[k] = arr[k-1];
                    break;
                }
            }
        }
        else
            continue;
        arr[index] = elem;
    }
    cout<<"\nThe New Array (Sorted Array):\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
    return 0;
}

This program was built and runs under the Code::Blocks IDE. Here is its sample run:

C++ program insertion sort

Now supply the size, say 10, for the array, and press ENTER. Here is the output you will see:

insertion sort in c++

Now supply any 10 numbers as 10 array elements, say 10, 1, 9, 2, 8, 3, 7, 4, 6, and 5, one by one. After supplying all 10 inputs, press the ENTER key to sort and print the new array as shown in the output given below:

c++ insertion sort

The following is how the above program's dry run (receiving user input) goes:

And the dry run of insertion sort code in the above program with user input, 10 as size, and 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 as elements of the array, goes like this:

Print the array after each sort

After each insertion sort sort, a new array is printed in this program. After watching the output of this program, you can understand its in-depth detail in sorting the elements.

#include<iostream>
using namespace std;
int main()
{
    int arr[50], tot, i, j, k, elem, index;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    for(i=1; i<tot; i++)
    {
        elem = arr[i];
        if(elem<arr[i-1])
        {
            for(j=0; j<=i; j++)
            {
                if(elem<arr[j])
                {
                    index = j;
                    for(k=i; k>j; k--)
                        arr[k] = arr[k-1];
                    break;
                }
            }
        }
        else
            continue;
        arr[index] = elem;
        cout<<"\nStep "<<i<<": ";
        for(j=0; j<tot; j++)
            cout<<arr[j]<<"  ";
    }
    cout<<"\n\nThe New Array (Sorted Array):\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
    return 0;
}

Here is its sample run with the same user input as provided in the previous program's sample run:

insertion sort c++

Insertion Sorting with a Function

This is the last program in this article that does the same job as the very first program in this article. The only difference is that this program uses a user-defined function, insertionSort(), to sort an array entered by the user.

This function receives an array and its size as its two arguments.

#include<iostream>
using namespace std;
void insertionSort(int [], int);
int main()
{
    int arr[50], tot, i;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    insertionSort(arr, tot);
    cout<<"\nThe New Array (Sorted Array):\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
    return 0;
}
void insertionSort(int arr[], int tot)
{
    int i, elem, j;
    for(i=1; i<tot; i++)
    {
        elem = arr[i];
        j = i-1;
        while((elem<arr[j]) && (j>=0))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = elem;
    }
}

Here is its sample run with user input, 10 as size, and 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 as elements for the array:

insertion sort using function c++

The same program in different languages

C++ Quiz


« Previous Program Next Program »


Liked this post? Share it!