Insertion Sort

The Insertion Sort is very simple technique, it inserts each item in proper place in the final list. Insertion sort is less effective as compared to the other sorting technique. In this, the array elements are divided into two parts.

Insertion sort example

These are the insertion sorting technique.

Search for the element less than first element. A[1] < A[0], so interchange them.

Next search for the next element less than first element. A[2] < A[0], so interchange them.

Now no any element in the right which is less than the first element. Similarly, we repeat the same process for A[1], A[2] and A[3].

While sorting of A[3], we found A[3] > A[4], so we interchange them.

Finally, we get the sorted array element.

Complexity of Insertion sort

Suppose n is the number of elements in an array.

Best Time Complexity - O(n)
Worst Time Complexity - O(n2)
Average Time Complexity - O(n2)

Insertion sort program in C

#include <stdio.h>
 
int main()
{
	int count, array[100], x, y, temp;

	printf("Enter the number of elements: \n");
	scanf("%d", &count);

	printf("Enter %d numbers \n", count);

	for (x = 0; x < count; x++)
	scanf("%d", &array[x]);

	for (x = 1 ; x <= count - 1; x++) {
	y = x;

	while ( y > 0 && array[y-1] > array[y]) {
		temp       = array[y];
		array[y]   = array[y-1];
		array[y-1] = temp;
		y--;
	}
	}

	printf("Insertion Sorted List:\n");

	for (x = 0; x <= count - 1; x++) {
	printf("%d\n", array[x]);
	}

	return 0;
}

Output of the above program :

Enter the number of elements: 
10
Enter 10 numbers 
54
32
21
98
76
54
87
36
52
28
Insertion Sorted List:
21
28
32
36
52
54
54
76
87
98