Insertion Sort in C is a simple and efficient sorting algorithm, that creates the final sorted array one element at a time. It is usually implemented when the user has a small data set. I’ll cover the following topics:
- What is Insertion Sort?
- Brief Working and Complexity
- Algorithm for Insertion Sort in C
- Insertion Sort in C
What is Insertion Sort?
Insertion Sort is a sorting algorithm where the array is sorted by taking one element at a time. The principle behind insertion sort is to take one element, iterate through the sorted array & find its correct position in the sorted array.
Insertion Sort works in a similar manner as we arrange a deck of cards.
Brief Working and Complexity
In each iteration, it compares the current element with the values in the sorted array. If the current element is greater than the element in the array, then it leaves the element and iterates to the next array element. Otherwise, if the current element is smaller than the array element then it moves the rest of the element in the array by one position and makes space for the current in the sorted array.
This is how Insertion sort takes one input elements at a time, iterates through the sorted sub-array and with each iteration it inserts one element at its correct position. This is why the algorithm is known as Insertion sort.
As the average & worst-case complexity of this algorithm are O(n2), where n is the number of elements, Insertion sort is not good for large data sets.
Algorithm for Insertion Sort
Step 1 − If the element is the first one, it is already sorted.
Step 2 – Move to next element
Step 3 − Compare the current element with all elements in the sorted array
Step 4 – If the element in the sorted array is smaller than the current element, iterate to the next element. Otherwise, shift all the greater element in the array by one position towards the right
Step 5 − Insert the value at the correct position
Step 6 − Repeat until the complete list is sorted
To understand how Insertion sort works, refer to the below image.
Let’s understand how insertion sort is working in the above image.
- 122, 17, 93, 3, 36
for i = 1(2nd element) to 36 (last element)
i = 1. Since 17 is smaller than 122, move 122 and insert 17 before 122
- 17, 122, 93, 3, 36
i = 2. Since 93 is smaller than 122, move 122 and insert 93 before 122
- 17, 93,122, 3, 36
i = 3. 3 will move to the beginning and all other elements from 17 to 122 will move one position ahead of their current position.
- 3, 17, 93, 122, 36
i = 4. 36 will move to position after 17, and elements from 93 to 122 will move one position ahead of their current position.
- 3, 17, 36, 93 ,122
Now that we have understood how Insertion Sort works, let us quickly look at a C code to implement insertion sort
Insertion Sort Function
void insertionSort(int array[], int n)
{
int i, element, j;
for (i = 1; i < n; i++) { element = array[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key by one position */ while (j >= 0 && array[j] > element) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = element;
}
}
Insertion Sort in C: Code
#include <math.h>
#include <stdio.h>
// Insertion Sort Function
void insertionSort(int array[], int n)
{
int i, element, j;
for (i = 1; i < n; i++) { element = array[i]; j = i - 1; while (j >= 0 && array[j] > element) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = element;
}
}
// Function to print the elements of an array
void printArray(int array[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", array[i]);
printf("n");
}Now after executing the above C program you would have understood how Insertion Sort works & how to implement it in C language. I hope this blog is informative and added value to you. With this, we come to an end of this Insertion Sort in C article.
Check out the Java training by Edureka, a trusted online learning company with a network of more than 250,000 satisfied learners spread across the globe. Edureka’s Java J2EE and SOA training and certification course is designed for students and professionals who want to be a Java Developer. The course is designed to give you a head start into Java programming and train you for both core and advanced Java concepts along with various Java frameworks like Hibernate & Spring.