Updated March 30, 2023
Introduction to Insertion Sort in C
Insertion sort is a sorting algorithm that helps in sorting objects of an array one by one. Insertion sort works by picking one element at a time and places it accordingly in the array. It will keep working on single elements and eventually put them in the right position, eventually ending with a sorted array. It is similar to sorting cards in hand, where we sort the cards one at a time. When the first card is sorted, we move to the next one and place it in a way where it appears sorted. First, let us have a look at the syntax and few examples. In this topic, we are going to learn about Insertion Sort in C.
Syntax
There is no particular syntax for writing the insertion sort but an algorithm. This algorithm can be as below to sort an array in ascending order.
- Traverse from array position 0 to array position 1 in the array.
- Now compare the current element of the array with its predecessor.
- If a current element of the array has a lesser value than the predecessor, then you can compare the previous number and then move the elements a position ahead of the previous number. This is similar to swapping the numbers and bringing the number to the expected position.
How to perform Insertion sort in C?
Insertion sort functions in the following way. The figure below explains the working of the insertion sort.
We have an array of 6 numbers which is not in a sorted manner. We need to sort this array using insertion sort. We first consider 85 and assume that it is sorted. We compare it with 12. 12 is smaller than 85; it will be swapped with 85 and placed in the first position. The second comparison will now be done using 85 again. 85 will be compared with 59. Again 59 is smaller than 85. These two numbers will be swapped again, and at the second position in the array, we will have 59 moving 85 to the third position. The iteration will check between the numbers 12 and 59. 12 is less than 59 and is already in the first position. Hence there will be no change in these two numbers. The next two numbers for comparison are 85 and 45. 45 is smaller than 85, and hence it will be swapped with 85. Next, it will be checked with 59. 45 is smaller than 59 as well; hence it will be swapped with 59 as well. Now 12 is smaller than 45; hence its position remains unchanged. Again the next iteration takes into consideration 85 with 72. 72 being smaller will be swapped with 85. 59 is smaller than 72; hence its position remains unchanged. Now 85 will be compared with 51. 51 will be swapped and will be compared with 72. Since 72 is bigger, it will be swapped again. 51 is smaller than 59 as well, so it will be getting swapped again. Now 51 is not smaller than 45; hence it will stay at its original position. You can now observe that the array is now sorted. All numbers are in ascending order.
Example:
Let us check this example now using the C program
#include <math.h>
#include <stdio.h>
/*C function to sort an array*/
void Sort_Insertion(int array[], int n)
{
int m, k, p;
for (m = 1; m < n; m++) {
k = array[m];
p = m - 1;
while (p >= 0 && array[p] > k) {
array[p + 1] = array[p];
p = p - 1;
}
array[p + 1] = k;
}
}
void print(int array[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int array[] = { 17, 78, 56,32 , 46 };
int n = sizeof(array) / sizeof(array[0]);
Sort_Insertion(array, n);
print(array, n);
return 0;
}The C program above has a main function which is called at the very beginning of any program. The main() program has an array containing an array of 5 elements which are in jumbled format. It then takes the size of the array by using the sizeof() function and size of the element at the 0th position. It will be then sent to a function sort_insertion which has arguments of the array and n elements. The control then moves to this function. This function takes three variables m, k, and p. The array is traversed till the second last element in a loop. The while loop moves the pointer from 0 to p-1 position. Here the numbers are greater than k and moved to a position that is ahead of their current position. Whenever the numbers are smaller, they are swapped, and k has the value of the new number. This function runs until the array is in a sorted manner. The for loop here performs this activity. While loop is comparing and swapping the numbers. After this, the print function is called, where every element of the sorted array is getting printed. A for loop is used here, starting from the 0th position of the array till the end of the array. All elements of the array will be printed post the sort function.
The output of this function will be as below.
The above array is in a sorted form now. Previously all numbers were randomly placed. Now using C language, the array is sorted.
Conclusion
There are many sorting techniques, out of which insertion sort is considered to be one of the simplest ones. Insertion sort compares two numbers and swaps the numbers when they are not in order. It will traverse the entire array for all the numbers until all of them are placed in proper order. This algorithm considers one element at a time and works accordingly. If the element is in the correct position, it will not swap the element and move to the next element. Using C language, this logic can be applied easily by using for and while loops. Thus insertion sort is one of the simplest sorting methods which sorts all elements of an array.
Recommended Articles
This is a guide to Insertion Sort in C. Here we discuss How to perform Insertion sort in C along with the example and output. You may also have a look at the following articles to learn more –
