What is Insertion Sort in C?
The sorting method called insertion sort matches every single element with adjacent ones as it iterates across an array. A smaller element than the one before it is inserted into the sorted subarray at the appropriate location.
To further illustrate, I have demonstrated an example in which I have considered an array of four elements in an array such as arr[]= {5, 4, 60, 9} and we want to sort this element in ascending order with using insertion sort. The following interactions explain the complete dry run of insertion sort:
Iteration 1
| 5 | 4 | 60 | 9 |
We have an array as arr[5, 4, 60, 9] now, in the first iteration of insertion sort we first compare the first two elements such as 5 and 4, As the arr[5] is > arr[4] so we swap them to sort the array in ascending order. Now, the array will be:
| 4 | 5 | 60 | 9 |
Iteration 2
| 4 | 5 | 60 | 9 |
In the second iteration, we compare the next two elements, such as arr[5] with arr[60].
As the arr[5] < arr[60] so swapping does not happen as it is already sorted in ascending order. Now, the array becomes:
| 4 | 5 | 60 | 9 |
Iteration 3
| 4 | 5 | 60 | 9 |
As in the third iteration, we match the third and fourth elements like arr[60] with arr[9].
Now, we see that the arr[60] > arr[9] so swapping occurs, then the array will sort in ascending order.
| 4 | 5 | 9 | 60 |
This is how insertion sort work in C which sorts an array element easily in ascending or descending order.
Flow-Chart of Insertion Sort
Following is the flowchart of the algorithm of insertion sort:
Implementing Example of Insertion Sort in C
We first require a collection of elements that need to be sorted in descending and ascending orders to build the insertion sort method in C. Assume for the purposes of this example that we’re dealing with an array of numbers {5, 4, 60, 9}:
void insertionsort_ascending(int arr1[], int n) {
int i, j, my_key;
//for loop is used to iterate the i values from 1 to i<n
for (i = 1; i < n; i++) {
my_key = arr1[i];
j = i - 1;
while (j >= 0 && arr1[j] > my_key) {
arr1[j + 1] = arr1[j];
j = j - 1;
}
arr1[j + 1] = my_key;
}
}
void insertionsort_descending(int arr2[], int m) {
int i, j, my_key;
//another for loop is created to iterate the i values from 1 to i<m
for (i = 1; i < m; i++) {
my_key = arr2[i];
j = i - 1;
while (j >= 0 && arr2[j] < my_key) {
arr2[j + 1] = arr2[j];
j = j - 1;
}
arr2[j + 1] = my_key;
}
}
int main() {
//Insertion-Sort with descending order
int my_arr[] = {5, 4, 60, 9}; //initialize an my_arr[] having four values
int m = sizeof(my_arr) / sizeof(my_arr[0]);
insertionsort_descending(my_arr, m);
printf("Sorted array in descending order: ");
for (int i = 0; i < m; i++)
printf("%d ", my_arr[i]);
printf("\n");
//Insertion-Sort with ascending order
int n = sizeof(my_arr) / sizeof(my_arr[0]);
insertionsort_ascending(arr2, n);
printf("Sorted array in ascending order: ");
for (int i = 0; i < n; i++)
printf("%d ", my_arr[i]);
printf("\n");
return 0;
}
In this code, two methods insertionsort_descending(), and insertionsort_ascending() take the array values of my_arr[]. The code then uses a for loop to iterate through the elements of the array.
We call both functions in the main function once they have sorted the arrays in descending and ascending order. After that, the for loops are used to print the sorted array.
When we run this program, the expected output is placed below:
Conclusion
The insertion sort is a quick and easy way to sort an array in either descending or ascending sequence. For small datasets, this sorting technique performs well. As you can see in the guide above, it is simple to implement an example of a C program to easily understand insertion sort in descending as well as ascending order.
