Insertion Sort In C++| Insertion Sort In C++ Example| Insertion Sort In C++ Program| Insertion Sort In C++ In Hindi

 

Insertion Sort In C++

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Algorithm

To sort an array of size n in ascending order:

1: Iterate from arr[1] to arr[n] over the array.

2: Compare the current element (key) to its predecessor.

3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Fig: Insertion Sort In C++

 

Program:

#include<iostream.h>

#include<conio.h>

void insertionSort(int arr[], int n)

{

          int i, key, j;

          for (i = 1; i < n; i++)

          {

                   key = arr[i];

                   j = i - 1;

                   while (j >= 0 && arr[j] > key)

                   {

                             arr[j + 1] = arr[j];

                             j = j - 1;

                   }

                   arr[j + 1] = key;

          }

}

void printArray(int arr[], int n)

{

          int i;

          for (i = 0; i < n; i++)

                   cout << arr[i] << " ";

          cout << endl;

}

void main()

{

          int arr[] = { 12, 11, 13, 5, 6 };

          int n = sizeof(arr) / sizeof(arr[0]);

          insertionSort(arr, n);

          printArray(arr, n);

getch();

}

Output:

5     6     11    12   13