Insertion Sort Program in C

In this article, we are going to learn how to code one of the most asked sorting algorithms, Insertion Sort in C Language. Starting with the intuition and approach for the problem before coding up the Insertion Sort Program in C. We will also be analyzing the complexity of the program for best and worst cases.

Understanding Insertion Sort

It is a stable and in-place sorting algorithm often used when comparison operations have a greater cost. Stable sort denotes that it maintains the ordering of elements while sorting and makes comparisons to position elements thereby requiring no extra space making it an in-place sorting algorithm. It is effective for small or partially sorted arrays in front of other advanced algorithms making it useful in terms of stability and simplicity.

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 this article, we learnt what insertion sort is and under what conditions it is a better option. Later, we moved towards understanding insertion sort with a dry run on an example array.

We also studied the algorithm and insertion program in C. At the end of this article on the insertion sort program in c, we analyzed the time and space complexity of insertion sort. Hope you found this article on insertion sort in c to be fruitful in helping you get the concept of the topic well. We expect to see you again at PrepBytes with another insightful article soon.

FAQs related to Insertion Sort Program in C

1. Which among them is better – Insertion Sort vs Bubble Sort?
Although both of them share the worst-case complexity of O(N^2). But insertion sort tends to be a better performer in terms of the number of operations performed to sort.

2. How is binary search effective when used together with insertion sort?
Binary Search can be used to find the exact location to insert an element on the sorted array.

3. Discuss the condition for the best and worst case time complexity of insertion sort?
Best Case Time Complexity of Insertion Sort is O(N) when the array is already sorted while the worst-case complexity jumps to O(N^2) in the worst scenario when an array is sorted but in reverse order.

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C
Doubly Linked List Program in C
FCFS Scheduling Program in C