Insertion Sort: Algorithm and Program in C

Insertion Sort is one of the simplest sorting algorithms that compare each array element with new elements that we want to insert in an array. It will insert a new element when the correct position is found because the array should maintain order.

Let’s understand it in brief

Suppose you have an array of 5 cards of a deck, and they are sorted in ascending order. Now you want to insert a new card and condition is all card should be in ascending order after insertion of the new card.

Now to insert a new card at the correct position, you have to start from the first card and then compare each card with a new card. Once you find the correct position, then you can insert the new card there. This procedure is followed by each element of the insertion sort to maintain the order of an array.

Insertion Sort Algorithm

Step 1. If there is only one element or the first element in an array, it behaves as a sorted array.
Step 2. Now pick the new element which you want to insert.
Step 3. Compare the new picked element with the sorted element of an array.
Step 4. Insert the value if the correct position is found.
Step 5. Repeat step 2 to step 4 until all element is inserted in an array.

How Insertion sort works with an example

Here we will sort the below array using selection sort.

First Pass

Second Pass

Third Pass

Fourth Pass

Fifth Pass

Pseudo-code of insertion sort

i ← 1
while i < length(A) x ← A[i] j ← i - 1 while j >= 0 and A[j] > x
A[j+1] ← A[j]
j ← j - 1
end while
A[j+1] ← x[3]
i ← i + 1
end while

Insertion Sort Program in C

#include<stdio.h>
#include<conio.h>
void main(){
    int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    for(i=1;i<n;i++){
        key=arr[i];
        j=i-1;
        while(j>=0 && arr[j]>key){
            arr[j+1]=arr[j];
            j=j-1;
        }
        arr[j+1]=key;
    }
    printf("\n");
    printf("after sorting:\n");
    for(i=0;i<n;i++){
        printf("%d\t",arr[i]);
    }
    getch();
}

Output:

Enter the number of elements you want to sort:
5
Now enter the 5 elements you want to sort: 
32
11
33
67
1
before sorting:
32      11      33      67      1 
after sorting:
1       11      32      33      67

Explanation of code

This program implements Insertion Sort in C. It starts by including stdio.h for input/output functions and conio.h for getch() to pause the screen. Inside main(), it declares an array arr[100] to store up to 100 numbers, loop counters i and j, n for the number of elements, and key as a temporary variable for sorting. The program first asks the user for the number of elements and then takes n inputs to fill the array. It prints the array before sorting. The sorting begins from the second element (i=1) and for each element, key stores the current value while j points to the element before it. A while loop shifts all elements greater than key one position to the right until the correct position for key is found, and then key is inserted at arr[j+1]. This process repeats for all elements, gradually building a sorted array. Finally, the program prints the sorted array, and getch() waits for a key press before closing the window.

Characteristics of Insertion Sort

• Insertion sort works perfectly for small data sets, but it takes time when the data set is large.
• It is inefficient for large data set.
• Insertion sort is a stable sorting technique because it does not change the relative order of elements.

Time & Space Complexity

Time Complexity

Space Complexity

Conclusion

Insertion sort is a simple sorting algorithm that works well for small sets of data. It builds the sorted list one element at a time by comparing and placing elements in the correct position. The program in C is easy to understand and shows clearly how the algorithm works step by step. Even though it is not very fast for large data, it is useful because it is easy to write, simple to use, and works well when the list is already almost sorted.