Insertion Sort in C++

Here we are going to learn how to implement Insertion Sort in C++.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

Insertion Sort in C++

‘Insertion Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,8,2,4}

  1. Compare the 2nd element with the 1st element and change their positions to sort in ascending (or descending) order if the 1st element is lesser (or greater) than the 2nd element
    1<8, hence no swapping, so array ->{1,8,2,4}
  2. Compare the 3rd element with the elements before it and change its position with the element that is greater (or smaller) than it and closest to the beginning of the array
    2<8 but 1<2, hence 2 and 8 are swapped, so array -> {1,2,8,4}
  3. Compare the ith element with the elements before it and change its position with the element that is greater (or smaller) than it and closest to the beginning of the array (note, ‘i’ takes values up till the length of the array)
    4<8 but 4<2, hence 4 and 8 are swapped, so array -> {1,2,4,8}
    Hence, the sorted array is -> {1,2,4,8}

How to implement insertion sort in C++

#include <stdio.h>
#define size 4 //pre-defining the array length for the program
void inputArray(int array[],int length)
 {
     printf("Input %d (integer) elements: ",length);
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        scanf("%d",&array[length]);
     }
 }
void printArray(int array[],int length)
 {
     printf("The elements of the given array are: ");
     for(int i=0;i<length;i++)printf("%d ",array[i]);
 }
//logic for insertion sort - treat the array like a deck of cards and place every element at position 'i' after comparing it with all the elements before it
 void insertionSort(int array[],int length)
  {
  	for(int i=1;i<length;i++){
  		int temporary=array[i];
  		int j;
//note, at every 'i' iteration of the first for loop, all successive elements before position 'i' which are greater than the element at position 'i' are being  pushed forward by one position and the gap which is created, then contains the element at position 'i'
  		for(j=i-1;j>=0 && array[j]>temporary;j--){
  			array[j+1]=array[j];
  		}
  		array[j+1]=temporary;
  	}
  }
int main()
{
    int array[size];//creating an integer array
    inputArray(array,size);//taking input in the array
    insertionSort(array,size);//sorting the array with the desired sorting algorithm
    printArray(array,size);//printing the array after sorting
    return 0;
}

Output:



Input 4 (integer) elements: 1 8 2 4

The elements of the given array are: 1 2 4 8

Summary:

  • inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • insertionSort(int[],int) is called to sort the elements of the array with the algorithm explained above
  • printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ after size can be changed to any other value in order to get the desired array-length
  • since (in C++) arrays are passed by reference, therefore the changes made in insertionSort(int[],int) stay permanently
  • Change the sign from ‘>’ to ‘<‘ in the second logical condition of the 2nd for loop to sort in descending order

Read more tutorials:

Leave a Reply

Your email address will not be published. Required fields are marked *