Insertion Sort C is one of the simplest and most recognizable sorting algorithms. It is sometimes used to refer to how we sort playing cards on our hands. As applied in programming, this algorithm sorts elements in an array. Despite being less efficient for large data, Insertion Sort can be considered efficient for small data or if the data is nearly sorted. One benefit of this particular algorithm is that it is easy to understand, making it suitable for beginners in sorting algorithms.
Insertion Sort operates on a clear principle: a given array is divided into two parts, the sorted part and the unsorted part. It starts with the sorted part containing only the first element of the array. It then moves to the unsorted part, selecting one element at a time and placing it in its correct position in the sorted part. This process is repeated until all elements of the array are sorted as desired, providing a clear and guided path to sorting.
Detailed Explanation of the Insertion Sort Algorithm
To understand Insertion Sort in C, let’s break down the algorithm into simple steps:
Start with the first element: The first element of the array is assumed to be sorted.
Pick the next element: Jump to the next element in the array.
Compare with sorted elements: The next step is to compare the picked element with elements in the sorted part of the array.
Shift elements if necessary: If the picked element is less than the sorted element, then move the sorted elements to the right side.
Insert the picked element: Place the selected element in its proper place.
Repeat: The same will be done for all elements in the unsorted part of the list.
This way, we are assured that the array gradually sorts itself, starting from the beginning as we reach the end.
Step-by-Step Example of Insertion Sort with a Unique Array
Consider the following array:
{50, 23, 9, 18, 61, 32}
We’ll sort this array step-by-step using Insertion Sort.
Initial Array:
Array: [50, 23, 9, 18, 61, 32]
The first element, 50, is assumed sorted.
First Pass:
Pick the second element: 23.
Compare 23 with 50: Since 23 is smaller, shift 50 to the right.
Insert 23 in the correct position.
Array: [23, 50, 9, 18, 61, 32]
Second Pass:
Pick the third element: 9.
Compare 9 with 50 and 23: Since 9 is smaller, shift 50 and 23 to the right.
Insert 9 in the correct position.
Array: [9, 23, 50, 18, 61, 32]
Third Pass:
Pick the fourth element: 18.
Compare 18 with 50, 23, and 9: Since 18 is smaller than 50 and 23 but larger than 9, shift 50 and 23 to the right.
Insert 18 in the correct position.
Array: [9, 18, 23, 50, 61, 32]
Fourth Pass:
Pick the fifth element: 61.
Compare 61 with 50, 23, 18, and 9: No shifting is needed since 61 is larger than all.
Insert 61 in the correct position.
Array: [9, 18, 23, 50, 61, 32]
Fifth Pass:
Pick the sixth element: 32.
Compare 32 with 61, 50, 23, 18, and 9: Since 32 is smaller than 61 and 50 but larger than 23, shift 61 and 50 to the right.
Insert 32 in the correct position.
Array: [9, 18, 23, 32, 50, 61]
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
Complete C Code Implementation for Insertion Sort
Here is the complete code:
#include <stdio.h>
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;
}
}
void printArray(int array[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", array[i]);
printf("n");
}
int main() {
int arr[] = {50, 23, 9, 18, 61, 32};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
printArray(arr, n);
insertionSort(arr, n);
printf("After sorting: ");
printArray(arr, n);
return 0;
}
Output:
Before sorting: 50 23 9 18 61 32
After sorting: 9 18 23 32 50 61
Explanation of Each Part of the Code
Let’s dissect the code to learn how it functions:
Including Standard I/O Library:
#include <stdio.h>
#include <stdio.h>
The standard input-output library is included so that printf can display the array.
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;
}
}
Parameters: The function requires two parameters: the array to be sorted and its size.
Loop Initialisation: The outer loop starts with the second element, in position i = 1, assuming the first element, at position i = 0, has already been sorted.
Inner Loop: This loop cycles through shifting elements as far right as the element to be placed at the correct position.
Insertion: The element is placed in the correct position it would occupy upon a sorting operation in the sorted part of the array.
Print Array Function:
void printArray(int array[], int n) {
for (int i = 0; i < n; i++)
printf(“%d “, array[i]);
printf(“n”);
}
This function is used to display the elements of the array.
It takes the array and cycles through it, and at the end of each iteration, it will print the element, and then a space is added.
Finally, it prints a newline character.
Main Function:
int main() {
int arr[] = {50, 23, 9, 18, 61, 32};
int n = sizeof(arr) / sizeof(arr[0]);
printf(“Before sorting: “);
printArray(arr, n);
insertionSort(arr, n);
printf(“After sorting: “);
printArray(arr, n);
return 0;
}
Array Initialisation: We define and initialise the array to be sorted.
Calculate Size: We calculate the number of elements in the array.
Print Before Sorting: The original array is printed.
Sort the Array: We call insertionSort to sort the array.
Print After Sorting: Finally, we call insertionSort to sort the elements of the given array.
It shows how Insertion Sort in C can be implemented and used in the C language most
efficiently.
Exploring the Advantages of Insertion Sort
Why should we consider using Insertion Sort in C? Let’s look at its advantages:
What are the reasons that make it beneficial for us to employ Insertion Sort? Let’s look
at its advantages:
Simplicity: There are no difficult steps to follow, and the algorithm is simple. It is easy to understand for anybody, even beginners.
Efficiency for Small Datasets: Using Insertion Sort in C with a small data set is desirable because this algorithm shows rather good
performance results. It is faster than many others, and linear algebra is more complicated in these cases.
Adaptive Nature: The algorithm works well in an almost ordered sequence. This means that the array, almost in order, required less
comparison change to reach the final required positions.
In-Place Sorting: It requires no additional memory beyond the original array, making it space-efficient.
Stability: The Insertion Sort is stable. It retains the invoked items’ relative positioning regarding their unique key.
Thanks to these benefits, Insertion Sort remains a credible instrument in particular cases, such as sorting small or partially sorted lists.
Identifying the Disadvantages of Insertion Sort
While Insertion Sort in C has its advantages, it also has some significant
drawbacks:
Inefficiency for Large Datasets: In general, Insertion Sort is very slow for large sets of elements. The function has a quadratic time
complexity ‘O(n^2)’, which makes the program slow as the number of elements grows.
High Time Complexity: It is less efficient than other sorting algorithms and takes quadratic time for execution, which is not as efficient as quick sort or merge sort.
Not Suitable for Random Large Datasets: Compared to other sorting algorithms, Insertion Sort in C is a relatively slow method in random data, especially when a large number of unsorted data is present.
Comparison to Other Algorithms: Other sorting algorithms, such as quicksort, mergesort, and heapsort, are considerably efficient for larger sets of data and provide better average and worst-case time complexity in their solutions.
However, these drawbacks do not limit the use of Insertion Sort because it is rather effective for sorting small data sets and is easy to implement.
Recognising the complex nature of Insertion Sort in C is essential for understanding when to use it. Let’s examine how it performed in various situations.
Best Case Complexity
Scenario: The array is already sorted.
Time Complexity: O(n)
Explanation: In the best case, each element is compared with a maximum of one different element. In this case, no shifts are needed for the algorithm, making it perform in linear time.
Worst Case Complexity
Scenario: The array is sorted in reverse order.
Time Complexity: O(n^2)
Explanation: Each element must be compared with all the previous elements and, hence, a maximum number of shifts. This quadratic time complexity makes it so inefficient where large datasets are involved.
Average Case Complexity
Scenario: The array elements are in random order.
Time Complexity: O(n^2)
Explanation: On average, each element will be compared with half of the previous elements in the list; hence, it has quadratic time
complexity.
Additional Information and Insights about Insertion Sort
Let us look at other views and types to better understand Insertion Sort.
Binary Insertion Sort for Improved Performance
An optimization technique that can be applied to Insertion Sort to maximise its efficiency involves using binary search. Binary Insertion Sort sorts the list by using a binary search algorithm to determine where the next element should be inserted, decreasing the number of matching operations required.
Steps to implement Binary Insertion Sort:
Binary search should be employed to determine the position of the current element relative to the sorted part of the array.
Slide all items greater than the current element to the right side of the array.
Place the current element in the correct place.
This modification makes the comparison faster, but the shifting operation takes O(n^2)
time.
Boundary Cases for Best and Worst Scenarios
Understanding the boundary cases makes it easier to assess Insertion Sort’s performance in different scenarios.
Best Case: The given array is already sorted. In this case, Insertion Sort in C takes O(n) time complexity because we don’t need any
shifting.
Worst Case: The array is sorted in descending order. In this case, every element has to be compared with all other elements, which takes O(n^2) as time complexity.
Algorithmic Paradigms Used in Insertion Sort
Insertion Sort employs several algorithmic paradigms:
Incremental Approach: It creates a sorted array incrementally, adding one element at a time into the array.
In-Place Sorting: It rearranges the various items in an array in a sorted form without using extra space.
Stable Sort: It maintains the relative order of equal elements.
That is why these paradigms make Insertion Sort applicable for certain particular
uses.
Application of Insertion Sort for Linked Lists
Insertion Sort can also be used in linked lists. Unlike arrays, elements in the linked list do not need to be shifted, making inserting more efficient.
Traverse the list to select the elements one by one.
For each element, find its correct position in the sorted part of the list.
Insert the element in its correct position.
Sorting linked lists using Insertion Sort is particularly efficient due to the direct
insertion without shifting.
Key Differences Between Insertion Sort and Other Algorithms
Other algorithms prove more efficient than Insertion Sort in C for larger datasets, even
though the implementation of this sorting algorithm is very straightforward and makes it very suitable for
processing small datasets.
Quicksort: These are time complexities of Quicksort that are much better with average and worst-case time complexities of O(n log n). It works in a divide-and-conquer fashion.
Mergesort: Although it is reliable and ensures O(n log n) time complexity, mergesort takes extra memory to merge.
Heapsort: Heapsort also takes O(n log n) time but is not a stable sorting algorithm.
Conclusion
Insertion Sort in C is a very simple and easy-to-understand data sorting method. It is widely used for small or nearly sorted datasets. In this blog, we understand how it works step-by-step, wrote the code in C language, and also explored the advantages and disadvantages of this method.
Because of its adaptive and stable nature, it is used in several fields and contexts. But, one should keep in mind that it is not a suitable method to deal with larger amounts of data.
So, it is very important to understand the pros and cons of Insertion Sort with respect to other sorting methods. On this basis, we can choose the perfect data sorting method to deal with various real life problems.
FAQs
Is Insertion Sort a Stable Algorithm?
Yes, Insertion Sort is a stable sorting algorithm. It preserves the relative order of equal elements in the sorted result as they were in the input stream.
What is the Space Complexity of Insertion Sort?
The space complexity of Insertion Sort in C is constant or O(1). The algorithm is an in-place sorting algorithm and, therefore, does not require any auxiliary space other than the space provided by the array.
Can Insertion Sort Be Used for Large Datasets?
Insertion Sort is not very efficient for large records since its time complexity is represented by O(n^2). It is more effective when used on small or nearly sorted lists.
What is Binary Insertion Sort?
A modification of Insertion Sort called Binary Insertion Sort uses binary search to determine the ideal location for inserting every element. While this increases comparison efficiency, moving items takes O(n^2) time.
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
