codescracker
c++

C++ Program for Insertion Sort



« Previous Program Next Program »

In this article, you will learn and get code to sort an array using insertion sort technique in C++. Here are the list of programs on insertion sort:

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

Insertion Sort in C++

To sort an array using insertion sort technique in C++ programming, you have to ask from user to enter the size for an 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 it answer:

// Insertion Sort Program in C++
// ----codescracker.com----

#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 build and run under Code::Blocks IDE. Here is its sample run:

C++ program insertion sort

Now supply the size say 10 for the aray, 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, 5 one by one. After supplying all the 10 inputs, press ENTER key to sort and print the new array as shown in the output given below:

c++ insertion sort

The dry run of above program (of receiving inputs from user) goes like:

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

Print Array after each Sort

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

// C++ Print Array after Each Sort
// ----codescracker.com----

#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 same user input as provided in previous program's sample run:

insertion sort c++

Insertion Sort using Function

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

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

// C++ Insertion Sort using Function
// ----codescracker.com----

#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++

Same Program in Other Languages

C++ Online Test


« Previous Program Next Program »



© Copyright 2021. All Rights Reserved.

CodesCracker