Home » Insertion sort algorithm

AlgorithmsData structures

Insertion sort algorithm

Arpit Jain

May 19, 2021

0

SaveSavedRemoved 0

Definition of insertion sort

Insertion sort algorithm is count in simple sorting algorithms. This sorting algorithm sorts the array by shifting elements one by one. It builds the final sorted array by shifting one item at a time. Time complexity is O(n²). Space complexity is O(1) because an extra variable key is used.

Topics Covered

• Definition
• Example of insertion sort with diagram
• Algorithm for insertion sort
• C program to implement insertion sort
• C++ program to implement bubble sort

Properties of insertion sort

• Insertion sort algorithm has one of the simplest implementations among all other sorting algorithms.
• It is efficient for smaller data sets but is not efficient for larger data sets or lists.
• Insertion sort also has less space complexity like bubble sort. It requires a single additional memory space.
•  Insertion sort algorithm does not change the relative order of elements with equal keys because it is stable in nature.

Example of insertion sort algorithm

The diagram below shows how the insertion sort works:

As shown in diagram, the insertion sort works same like the way we arrange playing cards in our hands. It always starts with the second element as the key element. The key element is compared with the elements ahead of it and then put it at the right place.

In the above example, the element 40 has nothing before it. The next element 10 is compared to 40 and is inserted before 40. Element 9 is smaller than both 40 and 10, so it is inserted before 10 and this operation continues until the array is sorted in ascending order.

Algorithm for insertion sort

insertionsort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastsortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionsort

C program to implement insertion sort

#include <stdio.h>
#include <conio.h>
// Function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("\n");
}
void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;
    // Compare key with each element on the left of it until an element smaller than
 it, is found.
    // For descending order, change key <array[j]> to key <array[j+1]>.
    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}
// Driver code
int main() {
  int data[] = {9, 5, 1, 4, 3};
  int size = sizeof(data) / sizeof(data[0]);
  insertionSort(data, size);
  printf("Final Sorted array in ascending order:\n");
  printArray(data, size);
}

C++ program to implement insertion sort

#include<iostream>
using namespace std;
int main()
{
	int n;
	cout<<"Enter the value of array size ";
	cin>>n;
	int arr[n];

        //apply the loop for taking the input in the array
        cout<<"Enter the values in the array :"<<endl;

	for(int i=0; i<=n; i++ )
	{
		cin>>arr[i];
	}
	//apply two loops for bubble sorting
	for(int i=1; i<=n; i++)
	{
		int current = arr[i];
		int j=i-1;
		while(arr[j]>current && j>=0)
		{
			arr[j+1]=arr[j];
			j--;
		}
		arr[j+1]=current;
	}
	//apply the loop for printing the final sorted array
                cout<<"The sorted array is :"<<endl;
		for(int i=0; i<=n; i++ )
	{
		cout<<arr[i]<<endl;
	}
	return 0;
}

You can try the practical of bubble sort on the virtual labs that provide some better understanding.