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

Page Contents

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

### Insertion sort program in c

```#include <stdio.h>
int main()
{
int n, array, 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;
}
```

### 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)