One-Stop Solution to Implement the Insertion Sort Algorithm in C

In C programming, sorting algorithms organize elements in a specific order. In other words, sorting means arranging the data or element in ascending or descending order to access it more efficiently. The unsorted elements are arranged in an organized manner, with one element at a time after every iteration. C provides many techniques for sorting the elements: bubble sort, selection sort, insertion sort, etc.

This article by Simplilearn will help you understand on insertion sort algorithm in detail.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

What Is the Insertion Sort Algorithm in C?

In the insertion sort algorithm, the sorting is done in ascending or descending order, one element at a time. In other words, when the given array of elements is unsorted, the elements are placed at the proper position one element at a time using the insertion sort algorithm. Finally, the sorted elements are represented in an array. 

Let’s look at the working of the insertion sort algorithm with an example.

How Does the Insertion Sort Work in C?

Let’s understand the working of insertion sort with an example.

Example: 

The elements to be sorted are:

Insertion_Sort_Algorithm_in_C_1

Pass 0: Place the first element 36 at position a[0], and the first element is sorted.

Insertion_Sort_Algorithm_in_C_2

Pass 1: Next, the second element 57 is compared with the first element a[0] e,i. element 36. Since element 57 > 36, the elements are already sorted.

Insertion_Sort_Algorithm_in_C_3

Two elements from the list of given elements are already sorted. 

Pass 2: In the 2nd pass, the 3rd element, a[2], is compared with the first element, a[0], first, and then the second element, a[1]. The element 20 is less than element 36 (20 < 36), so the element 20 is placed at the index a[0], and the rest of the elements are shifted towards the right side by one position.

Insertion_Sort_Algorithm_in_C_4

Insertion_Sort_Algorithm_in_C_5

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Pass 3: In the 3rd pass, element 52 is compared with all the first three elements. 

Element 52 is first compared with element 20. Since 52 > 20, nothing can be done.

Insertion_Sort_Algorithm_in_C_6

Next, element 52 is compared with the second element, a[1], 52 > 36; again there is no, change.

Insertion_Sort_Algorithm_in_C_7

Later, it is compared with the 3rd element 57, 52 < 57, so now,  52 is placed at position a[2], and element 57 is shifted to the right by one position.


Insertion_Sort_Algorithm_in_C_8

Insertion_Sort_Algorithm_in_C_9

Insertion_Sort_Algorithm_in_C_10

All four elements are sorted, and now we are left with the last element.

Full Stack Java Developer Course

In Partnership with HIRIST and HackerEarthEXPLORE COURSE
Full Stack Java Developer Course

Pass 4: Finally, the last element, 73 is compared with a[0], a[1], a[2], and finally with a[3]. Since the last element, 73, is greater than all other elements, it is placed at the last position, a[4].

Insertion_Sort_Algorithm_in_C_11.

The sorted elements are:

Insertion_Sort_Algorithm_in_C_12

How to Implement the Insertion Sort Algorithm?

Insertion Sort Algorithm

Step 1: First element a[0] is already sorted

Step 2: Move to the second element 

Step 3: The second element is compared with the first element

Step 4: If the second element is less than the first element, then shift the first element to the right by one position 

            if (key_ele <array[j])

            array[j+1]=array[j]

Step 5: Place the element in the position 

            array[j+1]=key_ele

Step 6: Repeat the steps until the array of elements is sorted correctly. 

Now we know the insertion sort algorithm.

Moving ahead, let’s understand the logic with the help of pseudo code.

Pseudo Code of Insertion Sort

Procedure:

insertionsort(Array: array of elements)

Int position

Int elementToInsert

For i=1 To length(num) include do:

valueToInsert = Array[i]

position =i-1

While position > 0 and Array[position]> elementToInsert do:

Array[position+1] =Array[position]

Position = position-1

End while

// insert element in position

Array[position+1]=elementToInsert 

End for 

End procedure

Up next, you have the insertion sort program.

Program to Sort Elements in Ascending Order:

#include <stdio.h>

#include<math.h>

void insertion_sort(int array[], int num)

{

int i, key_ele, k;

for (i = 1; i < num; i++)

{

   key_ele = array[i];

   k = i - 1;

     while (k >= 0 && array[k] > key_ele)

     {

        array[k + 1] = array[k];

        k = k - 1;

      }

array[k + 1] = key_ele;

}

}

int main()

{

int i;    

int arr[] = { 6, 5, 4, 2, 3 };

int size = sizeof(arr) / sizeof(arr[0]);

printf("Array before sorting:\n");

for (i = 0; i < size; i++)

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

printf("\n");

insertion_sort(arr, size);

printf("Array after sorting:\n");

for (i = 0; i < size; i++)

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

printf("\n");

return 0;

}

Output:

Insertion_Sort_Algorithm_in_C_13

So far, you have looked at the implementation of the insertion sort algorithm. 

Now, go ahead and take the next step and learn the advantages and disadvantages of the insertion sort algorithm in C.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Advantages of Insertion Sort in C

  • It is more efficient while working on a small list of array elements.
  • Storage space required for the insertion sorting algorithm is minimal.
  • It won’t consume more time performing on already sorted array elements.

Disadvantages of Insertion Sort in C

  • The insertion sort algorithm cannot be performed when the list of array elements is large.
  • It displays the worst-case time complexity of 0(n2)

With that, you can conclude this tutorial on Insertion Sort Algorithm in C. 

If you're eager to gain the skills required to work in a challenging, rewarding, and dynamic IT role - we've got your back! Discover the endless opportunities through this innovative Post Graduate Program in Full Stack Web Development course designed by our partners at Caltech CTME. Enroll today!

Next Steps

"Sorting Algorithms in C" can be your next topic. So far, you have learned the Insertion Sort Algorithm in C. The next fundamentals will be the data structures and the varieties in data structures used for different purposes.

If you are interested in software development, you can explore Simplilearn's courses that will give you the work-ready software development training you need to succeed today. Are you looking for a comprehensive training program in today's most in-demand software development skills, tools, and languages? Our Post Graduate Program in Full Stack Web Development should be the right thing for your career. Explore the course and enroll soon.

Please let us know in the comment section below if you have any questions regarding the “Insertion Sort Algorithm in C” tutorial. Our experts will get back to you at the earliest.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
  • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors