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