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.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

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:

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

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.

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.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

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.

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

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.

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

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

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].

The sorted elements are:

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:

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.

Master Core Java 8 Concepts, Java Servlet & More!

Java Certification TrainingENROLL NOW

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. 

Accelerate your career as a skilled MERN Stack Developer by enrolling in a unique Full Stack Developer - MERN Stack Master's program. Get complete development and testing knowledge on the latest technologies by opting for the MERN Stack Developer Course. Contact us 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 Full Stack Developer - MERN Stack 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.