Insertion Sort Algorithm in C

Insertion Sort is a simple and efficient sorting algorithm that works similarly to how you might sort playing cards in your hands. It builds the final sorted array one element at a time by repeatedly inserting each element into its correct position in the sorted portion of the array.

You can get the complete code from Github

How Insertion Sort Works:

1. Start with the second element of the array (since the first element is trivially "sorted").

2. Compare this element with the one before it. If the element is smaller, move the larger element one position to the right. Insert the current element into the correct position in the sorted portion of the array.

3. Repeat this process for each subsequent element, comparing and inserting it into the sorted portion of the array until the entire array is sorted.

insertionsort.c

1 #include<stdio.h>
2 int main() {
3     int Arr[] = {43,45,98,23,21,5,1,8,2,6,77,18,4};
4     int n = sizeof(Arr)/sizeof(Arr[0]);
5     int i,j,p,s;
6 
7     printf("Before Sort:\n");
8     for(i = 0;i < n;i++) {
9         printf("%d ",Arr[i]);
10     }
11     printf("\n");
12 
13     for(i = 1;i < n;i++) {
14         s = Arr[i];
15         for(j = i-1;j >= 0 && Arr[j] > s;j--) {
16             Arr[j+1] = Arr[j];
17             Arr[j] = s;
18             i = j - 1;
19         }
20     }
21 
22     printf("After Sort:\n");
23     for(i = 0;i < n;i++) {
24         printf("%d ",Arr[i]);
25     }
26     printf("\n");
27 
28     return 0;
29 }