Insertion Sort

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(n2).

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.

Figure of Sorting Technique

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 75
Code language: PHP (php)

Time and Space Complexity of Insertion Sort

Time Complexity
Worst CaseO(n2)
Best CaseO(n)
Average CaseO(n2)
Space Complexity
Worst CaseO(n2) total
O(1) auxiliary

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:-


Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. …
Read More

Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …
Read More

Sorting Algorithms

Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of sorting, types of sort. What is Sorting? Sorting refers to arranging data …
Read More

Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …
Read More

Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …
Read More

Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

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