Simple Insertion Sort Program in C++

Definition

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages like simple implementation, efficient for (quite) small data sets, more efficient in practice than most other simple quadratic algorithms, adaptive, stable, in-place; i.e., only requires a constant amount of additional memory space, online; i.e., can sort a list as it receives it.

Example Program

/* Simple Insertion Sort Program in C++*/
/* Data Structure C++ Programs,C++ Array Examples */

#include <iostream>
#include<conio.h>
#include<stdlib.h>

#define MAX_SIZE 5

using namespace std;

void insertion(int[]);

int main() {
    int arr_sort[MAX_SIZE], i, j, a, t;

    cout << "Simple C++ Insertion Sort Example - Array\n";
    cout << "\nEnter " << MAX_SIZE << " Elements for Sorting : " << endl;
    for (i = 0; i < MAX_SIZE; i++)
        cin >> arr_sort[i];

    cout << "\nYour Data   :";
    for (i = 0; i < MAX_SIZE; i++) {
        cout << "\t" << arr_sort[i];
    }

    for (i = 1; i < MAX_SIZE; i++) {
        t = arr_sort[i];
        j = i - 1;

        while (j >= 0 && arr_sort[j] > t) {
            arr_sort[j + 1] = arr_sort[j];
            j = j - 1;
        }
        arr_sort[j + 1] = t;

        cout << "\nIteration : " << i;
        for (a = 0; a < MAX_SIZE; a++) {
            cout << "\t" << arr_sort[a];
        }
    }

    cout << "\n\nSorted Data :";
    for (i = 0; i < MAX_SIZE; i++) {
        cout << "\t" << arr_sort[i];
    }

    getch();
}

Sample Output

Simple Insertion Sort Example - Array

Enter 5 Elements for Sorting
3244
23
12
34
1

Your Data   :   3244    23      12      34      1
Iteration 1 :   23      3244    12      34      1
Iteration 2 :   12      23      3244    34      1
Iteration 3 :   12      23      34      3244    1
Iteration 4 :   1       12      23      34      3244

Sorted Data :   1       12      23      34      3244

------------------
(program exited with code: 0)

Press any key to continue . . .