Insertion sort in Data structure is one of the simple sorting technique used for sorting the elements.

Insertion sort in Data structure

What is Insertion Sort?: Insertion sort is the algorithm in which elements are placed at its right place one at a time.

Insertion sort technique :
In this Insertion sort technique, Sorting of the element is performed by adding the element to the existing sorted list.
The main idea behind the insertion sort is to pick one element from the input array and place that element at its correct position in the sorted array.

How does insertion sort works?

In this technique initially, we are having only one element in a list after this we gradually insert a new element to list at its proper place in this way we will get our sorted list.
The insertion sort is mostly used when the number of elements in an array is small or It can be used when array elements are already sorted or some of the elements where misplaced.

Insertion sort example

1. Insert 70 to an array

Insertion Sort in Data Structure2. Insert 90.

Insertion Sort in Data Structure3. Insert 30

Insertion Sort in Data Structure4. Insert  100

Insertion Sort in Data Structure

5. Insert 40
Insertion Sort in Data Structure

In this way, we get our sorted array as 30 40 70 90 100.
Passes required for this sort is N.

Insertion sort algorithm

  1. If it is the first element, it is already sorted. return 1;
  2. Pick next element
  3. Compare with all elements in the sorted sub-list
  4. Shift all the elements in the sorted sub-list that is greater than the value to be sorted
  5. Insert the value
  6. Repeat until the list is sorted

Flowchart for Insertion sort

Flowchart for Insertion sort
Flowchart for Insertion sort

Insertion sort program in c

#include <stdio.h>
int main()
{
int n, array[1000], c, d, t;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++) {
scanf("%d", &array[c]);
}
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d] < array[d-1]) {
t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}

Output:

 

Insertion sort Complexity

The time complexity for Insertion sort
The worst-case and average-case time complexity for Insertion sort: O(n2).
The Best case complexity of selection sort: O(n2).
Space complexity for selection sort: O(1)

Advantages of Insertion sort

  • It is a very simple sorting technique to implement.
  • It has great performance if we have a small set of data.
  • The space required is small.

Disadvantages of Insertion sort

  • It is not as good as other sorting technique.
  • It is well for only a small set of data.
  • It required n2 steps for sorting N element.

Write A Comment