Insertion sort is a classical sorting algorithm, in which each element is compared with its previous elements. for example {1,3,5,34,6}. 3 is compared with 1 ,since 3 is greater than 1 no interchange is required.again 5 is compared with its previous element 1 and 3. as 5 is greater than both 1 and 3 nothing would happen. now 34 is compared with 1,3,5 and since all the elements are less than 34 ,nothing would happen.Again 6 is compared with 1,3,5,34. as 6 is less than 34, at the place of 34, 6 will be placed.

#include<stdio.h>

int main() {
	int arr[] = { 1, 3, 5, 34, 6 };
	int j = 0;
	int size_of_arr = sizeof(arr) / sizeof(arr[0]);

	for (j = 1; j < size_of_arr; j++) {
		int key = arr[j];
		int i = j - 1;
		while ((i > -1) && (arr[i] > key)) {
			arr[i + 1] = arr[i];
			i--;
		}
		arr[i + 1] = key;
	}

	/* print output*/
	int i = 0;
	for (i; i < size_of_arr; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

Insertion sort is an “in place” algorithm, no memory allocations are required.

Time Complexity:

O(N²)

 



Related Contents to follow