AppDividend
Latest Code Tutorials

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

0

C++ Insertion Sort Example | Insertion Sort Program In C++ is today’s topic. We are going to discuss insertion sort in C++, though this sorting technique is not that much efficient in comparison to other Sorting Algorithms like QuickSort, MergeSort, SelectionSort, HeapSort, it is suitable for a simple set of data like Quadratic sorting algorithms, etc.

C++ Insertion Sort

If we want to sort an array using insertion sort technique in C++ programming, you have to ask the user to enter the array size and array elements in random order, now start sorting the elements of the array in ascending order using insertion sort technique.

One can think insertion sort in such a way that we are playing cards in our hands.

We start with an empty set empty left side, and the cards laid down on the table.

After that, we choose one card from the table, and then we place it to its right position in sorted order. To sort we compare the cards with an already sorted card in our hand from right to left.

In the sense of an array we can assume that the first element A[0] in the array is already sorted in pass 1, then the second element A[1] is compared with the first element means with the sorted element and then inserted into its correct position either left of A[0] or right of A[0].

Then the third element A[2] in pass three is compared with A[1] and A[0] respectively and is inserted in the correct position and so on.

#Algorithm of Insertion Sort

See the following algorithm.

INSERTION_SORT (A, N)(Array starts from O)
Repeat Step 2 to 4 for K = 1, 3, ..., N-1:
 	Set KEY = A[K] and PTR = K - 1.
 	Repeat while KEY < A[PTR] and PTR>=O:
   	 (a) Set A[PTR+1] = A[PTR]
    		 (b) Set PTR = PTR - 1.
 	[End of Loop]
 	Set A[PTR+1] = KEY
    [End of Loop 2.]
 Return.

#Understanding Insertion Sort With an Example

Let say, 

Value 16 8 9 12
Index 0 1 2 3

 

Is an array of size 4. We have to sort it using Insertion Sort.

So, according to the algorithm, at the very first pass, the value of K=1, KEY=8, and PTR=(K-1)=0

Pass1: A[PTR]=16, as 8<16 the swap will be done. {8,16,9,12} this way 16 and 8 will be swapped and PTR=-1, so while loop will stop executing. Then A[PTR+1]=A[0]=KEY=8 will be assigned.

Pass2:  K=2, PTR= 1, KEY=9 and A[PTR]=16 . As 9<16 and PTR>=0 A[2] will be 16, {8,16,16,12} and PTR=0, then as KEY>A[PTR] means 9>8 no swap will be done.

So while loop will stop executing, and at last A[PTR+1] = A[1] will be set to 9. So the array after this swap will be:

{8,9,16,12}

Pass3: K=3, PTR=2, KEY=12, and A[PTR]=16. In while loop, as A[PTR]>KEY, we will set A[PTR+1] means A[3]=16 and PTR=(2-1)=1, so array will be {8,9,16,16}. Then, A[PTR] <KEY so nothing will be done and while loop will stop executing. Now, then the KEY value will be inserted at position PTR+1 means at position 2, A[2]=12.

So, after all, operation the FINAL SORTED ARRAY will be:

Value 8 9 12 16
Index 0 1 2 3

 

#Program of Insertion Sort

See the following program.

#include <bits/stdc++.h>
using namespace std;
void insertionSort(int arr[], int n)
{
  int k, key, ptr;
  for (k = 1; k < n; k++)
  {
    key = arr[k];
    ptr = k - 1;
    while (ptr >= 0 && arr[ptr] > key)
    {
      arr[ptr + 1] = arr[ptr];
      ptr = ptr - 1;
    }
    arr[ptr + 1] = key;
  }
}

int main()
{
  int n;
  cout << "Enter Size of the Array: ";
  cin >> n;
  int arr[n], i;
  cout << "Enter values of the array\n";
  for (i = 0; i < n; i++)
    cin >> arr[i];
  insertionSort(arr, n);

  cout << "Array after Insertion Sort is: ";
  for (i = 0; i < n; i++)
    cout << arr[i] << " ";
  return 0;
}

See the following output.

C++ Insertion Sort Example

#Time Complexity

The time complexity of the Insertion sort is O(n*2), and the auxiliary space used is O(1).

#Boundary Cases

Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

#Application

Insertion is mostly used in that place where the array was almost sorted, and the elements present in the array are small in number. Only in that place, Insertion Sort works efficiently; otherwise, other techniques are more efficient to work.

As the time complexity, in that case, is minimum and if the array is in reverse order, then insertion sort takes maximum time and hence time complexity increases.

Online: Insertion sort can sort a list as it receives it.

We can also use the binary search technique so that we have to make less comparison which we do in common insertion technique.

Standard Insertion Sorting takes O(i), but we can reduce it to O(log i) in the binary search technique.

Finally, C++ Insertion Sort Example | Insertion Sort Program In C++ is over.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.