C Programming

How to Implement Insertion Sort in C with Example

The sorting algorithm known as “Insertion Sort” is straightforward and effective for small datasets. It is a comparison-based method that arranges the elements by looping through an array, evaluating each element against those that came before it, and exchanging them if necessary. In this post, we will go over an example of how to implement the insertion sort in C language.

What is Insertion Sort in C?

The sorting method called insertion sort matches every single element with adjacent ones as it iterates across an array. A smaller element than the one before it is inserted into the sorted subarray at the appropriate location.

To further illustrate, I have demonstrated an example in which I have considered an array of four elements in an array such as arr[]= {5, 4, 60, 9} and we want to sort this element in ascending order with using insertion sort. The following interactions explain the complete dry run of insertion sort:

Iteration 1

5 4 60 9

We have an array as arr[5, 4, 60, 9] now, in the first iteration of insertion sort we first compare the first two elements such as 5 and 4, As the arr[5] is > arr[4] so we swap them to sort the array in ascending order. Now, the array will be:

4 5 60 9

Iteration 2

4 5 60 9

In the second iteration, we compare the next two elements, such as arr[5] with arr[60].

As the arr[5] < arr[60] so swapping does not happen as it is already sorted in ascending order. Now, the array becomes:

4 5 60 9

Iteration 3

4 5 60 9

As in the third iteration, we match the third and fourth elements like arr[60] with arr[9].

Now, we see that the arr[60] > arr[9] so swapping occurs, then the array will sort in ascending order.

4 5 9 60

This is how insertion sort work in C which sorts an array element easily in ascending or descending order.

Flow-Chart of Insertion Sort

Following is the flowchart of the algorithm of insertion sort:

Implementing Example of Insertion Sort in C

We first require a collection of elements that need to be sorted in descending and ascending orders to build the insertion sort method in C. Assume for the purposes of this example that we’re dealing with an array of numbers {5, 4, 60, 9}:

#include <stdio.h>

void insertionsort_ascending(int arr1[], int n) {

  int i, j, my_key;

//for loop is used to iterate the i values from 1 to i<n

  for (i = 1; i < n; i++) {

    my_key = arr1[i];

    j = i - 1;

    while (j >= 0 && arr1[j] > my_key) {

        arr1[j + 1] = arr1[j];

        j = j - 1;

    }

    arr1[j + 1] = my_key;

  }

}

void insertionsort_descending(int arr2[], int m) {

  int i, j, my_key;

//another for loop is created to iterate the i values from 1 to i<m

  for (i = 1; i < m; i++) {

    my_key = arr2[i];

    j = i - 1;

    while (j >= 0 && arr2[j] < my_key) {

        arr2[j + 1] = arr2[j];

        j = j - 1;

    }

    arr2[j + 1] = my_key;

  }

}

int main() {

  //Insertion-Sort with descending order

  int my_arr[] = {5, 4, 60, 9}; //initialize an my_arr[] having four values

  int m = sizeof(my_arr) / sizeof(my_arr[0]);

  insertionsort_descending(my_arr, m);

  printf("Sorted array in descending order: ");

  for (int i = 0; i < m; i++)

    printf("%d ", my_arr[i]);

  printf("\n");

  //Insertion-Sort with ascending order

  int n = sizeof(my_arr) / sizeof(my_arr[0]);

  insertionsort_ascending(arr2, n);

  printf("Sorted array in ascending order: ");

  for (int i = 0; i < n; i++)

    printf("%d ", my_arr[i]);

  printf("\n");

  return 0;

}

In this code, two methods insertionsort_descending(), and insertionsort_ascending() take the array values of my_arr[]. The code then uses a for loop to iterate through the elements of the array.

We call both functions in the main function once they have sorted the arrays in descending and ascending order. After that, the for loops are used to print the sorted array.

When we run this program, the expected output is placed below:

Conclusion

The insertion sort is a quick and easy way to sort an array in either descending or ascending sequence. For small datasets, this sorting technique performs well. As you can see in the guide above, it is simple to implement an example of a C program to easily understand insertion sort in descending as well as ascending order.

About the author

Kaynat Asif

My passion to research new technologies has brought me here to write for the LinuxHint. My major focus is to write in C, C++, and other Computer Science related fields. My aim is to share my knowledge with other people.