Insertion Sort

Last updated on September 4th, 2023 at 09:44 pm

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages..

What is Insertion sort?

Insertion Sort is a simple and efficient comparison sort. It works similarly as we sort cards in our hand in a card game.

The algorithm based on the idea that places an unsorted element at its suitable place in each iteration.

This sort algorithm with expensive runtime with O(n²).

Insertion Sort Algorithm

Every repetition of this sort removes an element from the input data and inserts it into the correct position in the already-sorted list until no input elements remain.

Implementation of Insertion Sort

Program Code in C :-

#include<stdio.h>

//function to print array
void printarray(int arr[], int n)
{
  for(int i=0; i<n; i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n");
}

void insertionSort(int arr[], int n)
{
  for(int i=0; i<n; i++)
  {
    int k = arr[i];
    int j = i-1;

    //compare key with each element on the left of it until an element 
    //smaller than it is found.
    while(k < arr[j] && j >=0)
    {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = k;
  }  
}

//Driver code
int main()
{
  int data[] = {4, 75, 74, 2, 54};
  int n = sizeof(data) / sizeof(data[0]);
  insertionSort(data, n);
  printf("Sorted array : ");
  printarray(data, n);
}
Code language: C++ (cpp)

Output :-

Sorted array : 2 4 54 74 75Code language: PHP (php)

Time and Space Complexity of Insertion Sort

Advantages of Insertion Sort

1. Simple implementation.
2. Efficient for small data.
3. Stable: Maintains relative order of input data if the keys are the same.
4. In-place requires only a constant amount O(1) of additional memory space.

Other Sorting Algorithms:-

• Bubble Sort
• Selection Sort
• Merge Sort
• Counting Sort
• Bucket Sort
• Radix Sort
• Quick Sort
• Heap Sort
• Shell Sort

Related:

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎