# insertion sort

*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.*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#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²)

## Leave a Reply