Insertion Sort

Insertion sort is a one of the sorting technique used for sorting the elements.

Insertion sort technique:-

In this Insertion sort technique, Sorting of the element is performed by adding the element to the existing sorted list.

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.

Example:-

1. Insert 70 to array.

        2. Insert 90.

        3. Insert 30 in array.

        4. Insert 100.

         5. Insert 40.

In this way we get our sorted array as 30 40 70 90 100.

Passes required for this sort is N.

The time complexity for Insertion sort is O(n²) for worst case.

Advantages of Insertion sort

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

Disadvantages of Insertion sort

1. It is not good as other sorting technique.
2. It is well for only small set of data.
3. It required n² steps for sorting N element.

Program

1234567891011121314151617181920212223242526272829303132333435

#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 of program:-

Enter number of elements:
5
Enter 5 integers
10 2 30 4 1
Sorted list in ascending order:
1
2
4
10
30