Insertion Sort Program in C

Last Updated on June 8, 2023 by Mayank Dham

This tutorial will teach you how to program in C using one of the sorting algorithms that is frequently requested. Before writing the C code for the Insertion Sort Program, start with your first thoughts and approach to the problem. Additionally, we will evaluate the program’s complexity in both the best and worst-case scenarios.

Understanding Insertion Sort

Insertion sort is a simple and efficient comparison-based sorting algorithm. It works by dividing the input array into two portions: a sorted portion and an unsorted portion. Initially, the sorted portion contains only the first element of the array, while the unsorted portion contains the remaining elements.
The algorithm iterates through the unsorted portion, taking one element at a time and inserting it into its correct position within the sorted portion. This process continues until all elements in the unsorted portion are exhausted, and the entire array becomes sorted

In insertion sort, we move one by one to the left of the array and on each iteration, we move right for the placement of elements in their correct position in any element that is not following the order. The process is kept repetitive until our outer loop reaches the last accessible index.

Dry Run of Insertion Sort Program in C

Now that we have clarity of the concept and working of the Insertion Sort program in C, let us take an example array and dry run with illustrations to understand the working in a step by step manner:-

Suppose we have an array [ 6,2,1,3,5 ], the insertion sort algorithm considers the first element is already sorted. There are going to be n-1 passes to sort the array in ascending order.

First Pass:

The second element i.e. 2 is compared to the first element 6, which is lesser, hence swapping is performed with the first pass making it [6,6,1,3,5], ending with the processed array [ 2,6,1,3,5 ]

Second Pass:

For this pass, the index will be at the 2nd position or 3rd element, as the swapping is valid now that 1>6, the array turns [2,6,6,3,5] and on the following iteration, the result of this pass is obtained as [2,2,6,3,5] and the final processed array obtained becomes [1,2,6,3,5]

Third Pass:

As the array up and until now is [1,2,6,3,5], 3 will be the key, with its transition being, [1,2,6,6,5] and result as [1,2,3,6,5] on the assignment of the key.

Fourth Pass:

The n-1th and also the last pass on this array of 5 elements, only one iteration will be possible with 5 replacing the second last element 6 i.e. [1,2,3,6,6] and assignment of the key to give us the obtained array in the form of [1,2,3,5,6] as the output.

Algorithm of Insertion Sort

The Selection Sort program in C to sort the array in ascending order can be implemented in a few easy steps as mentioned below:-

1. Declare an array of size, n.
2. Provide the n inputs such that the array (named arr) is unsorted.
3. Run a loop, with i from 0 to n-1
4. Assign arr[i] as key and i-1 as j
5. While j >= 0 and arr[j+1] > arr[j] is True
   • arr[j+1] = arr[j]
   • Increment j = j + 1
6. Assign key at a[j+1]

Program Code of Insertion Sort in C

We just discussed the algorithm to implement and now let us look at the code and study how we can do an insertion sort program in C.

#include <stdio.h>

void insertionSort(int arr[], int n)
{
    int i, key, j;
    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;
    }
}

int main()
{
    int i;
    int arr[] = {6,2,1,3,5};
    int n = 5;
  
    insertionSort(arr, n);
    for (i = 0; i < n; i++)
        printf("%d\n", arr[i]);
  
    return 0;
}

Output

1
2
3
5
6

Analysis of Insertion Sort Algorithm

The best case time complexity of insertion sort is O(N) under the condition that the array is already sorted while the worst case reaches up to O(N^2) and on deducing the average case, it goes on to be O(N^2) as well.

The space complexity of insertion sort remains O(1) as no extra auxiliary space is consumed on sorting the array.

Applications of Insertion Sort

It often comes into use to perform certain tasks, few examples where the algorithm is used are-

1. Insertion sort can be taken into consideration when sorting a deck of cards as it is similar to placing the unsorted cards in sorted order.

2. Insertion sort is often used to sort arrays of small lengths and is preferable for small databases.

Conclusion
In conclusion, insertion sort is a simple and intuitive sorting algorithm that builds the sorted portion of an array or list by inserting each element into its correct position. It has an average and worst-case time complexity of O(n^2), but it performs well on small or partially sorted arrays. Insertion sort operates in place, meaning it doesn’t require additional memory beyond the input array. While it may not be the most efficient choice for large data sets, it is easy to implement and understand.

FAQs related to Insertion Sort Program in C:

Q1. What is the best-case time complexity of insertion sort?
The best-case time complexity of insertion sort is O(n) when the input array is already sorted. In this case, each element only needs to be compared with its previous element before being placed in its correct position.

Q2. Can insertion sort handle large arrays efficiently?
Insertion sort has a time complexity of O(n^2), making it less efficient than algorithms like merge sort or quicksort for large arrays. However, it can be optimized with techniques like binary search for finding the correct position to improve performance.

Q3. Does insertion sort work for both ascending and descending order?
Yes, insertion sort can be modified to sort in either ascending or descending order. The comparison operation can be adjusted accordingly during the insertion process.

Q4. How does insertion sort compare to other sorting algorithms?
Insertion sort is simple to implement and performs well on small or partially sorted arrays. However, it is less efficient than more advanced algorithms like merge sort or quicksort for larger data sets. Other algorithms often have better average and worst-case time complexities.

Q5. Is insertion sort stable?
Yes, insertion sort is a stable sorting algorithm. Elements with equal values maintain their relative order after sorting.

Q6. Can insertion sort handle different types of data?
Yes, insertion sort can be used to sort various types of data as long as a comparison operation is defined for the elements being sorted.

Q7. Are there any advantages of insertion sort?
Insertion sort has a few advantages, such as simplicity, ease of implementation, and efficiency on small or partially sorted arrays. It is also an in-place sorting algorithm, meaning it doesn’t require additional memory beyond the input array.

Q8. When should insertion sort be used?
Insertion sort is suitable for small or partially sorted arrays, as well as situations where simplicity and ease of implementation are more important than absolute efficiency. It can be used as a stepping stone for more advanced sorting algorithms or for educational purposes.