Insertion sort is a fundamental sorting algorithm that is renowned for its simplicity and efficiency in sorting small lists. In this article, we’ll delve into how to implement the insertion sort algorithm in C. We’ll explore its working principles, discuss its efficiency, and walk through a step-by-step guide to coding this algorithm.
Understanding the Basics of Insertion Sort
Insertion sort works similarly to the way you might sort a hand of playing cards. It iterates through an array, and for each element, it finds the appropriate location within the sorted portion of the array and inserts it there. This process repeats until the entire array is sorted.
Advantages of Insertion Sort:
- Simple to implement: It’s straightforward and easy to understand.
- Efficient for small datasets: Ideal for sorting small arrays or lists.
- Stable: Maintains the relative order of equal elements.
- In-place: Requires minimal additional memory.
Step-by-Step Implementation in C
Setting Up the Environment: First, ensure you have a C programming environment set up. You can use any IDE or compiler that supports C.
The Code: Here is a basic implementation of the insertion sort algorithm in C:
#include <stdio.h>
void insertionSort(int array[], int size) {
int i, key, j;
for (i = 1; i < size; i++) {
key = array[i];
j = i - 1;
/* Move elements of array[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", array[i]);
printf("\n");
}
int main() {
int array[] = {12, 11, 13, 5, 6};
int n = sizeof(array) / sizeof(array[0]);
insertionSort(array, n);
printArray(array, n);
return 0;
}
Exploring the Code
How Does it Work?
- Iteration: The function
insertionSortiterates over the array. - Key Element: In each iteration, it selects an element (
key) and compares it with elements in the sorted section. - Shifting Elements: If a sorted element is larger than the
key, it is shifted one position ahead. - Inserting the Key: The
keyis then inserted in the correct position.
Analyzing the Efficiency
Time Complexity:
- Best Case (Already Sorted): O(n)
- Average and Worst Case (Reverse Sorted): O(n^2)
Space Complexity: O(1) – as it only requires a small, constant amount of additional space.
Conclusion and Further Exploration
In conclusion, insertion sort in C is a powerful algorithm for sorting small datasets. While it may not be as efficient as more complex algorithms like quicksort or mergesort for larger datasets, its simplicity and minimal memory usage make it a valuable tool in a programmer’s arsenal.
by the Bito team. 
