Insertion Sort in C++

What is Insertion Sort in C++?

Rearranging of data in a logical order is known as sorting i.e. arranging of data in ascending or descending order. In this article, we will learn about insertion sort in C++. Insertion sorting is done in a same way as we sort our cards in while we play game of cards. In this article we will learn more about insertion sort in C++.

insertion sort

Insertion Sort in C++

If there are n element and it requires (n-1) pass to sort them then, at each pass we insert current element in the appropriate position so that the element are in order. Some characteristics of insertion sort in C++.

  • A sub-list is maintained which is always in sorted order.
  • It is better then Selection Sort and Bubble Sort algorithms.
  • It is efficient for smaller data sets but inefficient for larger data sets.
  • Its space complexity is less.
  • It does not change the relative order of elements which are equal.
Insertion Sort In C++

Execution of insertion sort in C++

 

  • First we will  compare first element in the list with its adjacent element.

  • And at every comparison if the element can be inserted at a particular position, then it is inserted by shifting the other elements one position to the right.

  • The above steps are repeated until all the elements in the list are in their appropriate position.i.e. list is in sorted order.
Insertion Sort In C++

Algorithm for insertion sort in C++

  1. INSERTION-SORT(A)
  2. for i = 1 to n
  3. key ← A [i]
  4. j ← i – 1
  5. while j > = 0 and A[j] > key
  6. A[j+1] ← A[j]
  7. j ← j – 1
  8. End while
  9. A[j+1] ← key
  10. End for

Program for insertion sort in C++

#include <iostream>
using namespace std;

//Function to print array.
void display(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
    cout<< arr[i]<<"\t"; 
    cout<<"\n"; 
} 

//Main function to run the program.
int main() 
{ 
    int array[] = {5, 3, 1, 9, 8, 2, 4,7}; 
    int size = sizeof(array)/sizeof(array[0]); 

    cout<<"Before Insertion sort: \n";
    display(array, size);//Using dispaly function to print unsorted array.

    int i, target, j;  
    for (i = 1; i < size; i++) 
    {  
        target = array[i];  
        j = i - 1;  

        /* Here the elements in b/w arrary[0 to i-1]
        which are greater than target are moved
        ahead by 1 position each*/
        while (j >= 0 && array[j] > target) 
        {  
            array[j + 1] = array[j];  
            j = j - 1;  
        }  
        array[j + 1] = target;  
    }
    cout<<"After Insertion sort: \n"; 
    display(array, size);//Using dispaly function to print sorted array. 
    return 0; 
}
Output:
Before Insertion sort: 
5	3	1	9	8	2	4	7	
After Insertion sort: 
1	2	3	4	5	7	8	9	

Pros and Cons of Insertion Sort Algorithm

Pros

  • Anyone can write it is moderately easy to understand
  • Only O(1) space requirements
  • For smaller number of items in array its quicker than merge sort

Cons

  • Not so good average time complexity of O(n2)
  • If there are large elements then it gives bad performance because of O(n^2) time complexity
  • Shifting items because of insertion can be costly

Other information

  • Best Case: If already sorted data set
  • Worst Case: Sorted data set but in opposite order
Insertion Sort in C++ meme