Insertion Sort is a simple and intuitive sorting algorithm that builds the sorted array one element at a time. It works similarly to how people often sort playing cards in their hands: by taking one element at a time and inserting it at the correct position. Insertion Sort is efficient for small or nearly sorted datasets and is easy to implement.
Understanding the Problem
The algorithm iterates through the array, and for each element, it compares with the elements in the sorted portion to find its correct position. Each element is shifted until the proper position is found, and the current element is inserted there. This process is repeated for all elements, gradually forming a fully sorted array.
Program 1: Iterative Insertion Sort
This program demonstrates sorting an integer array in ascending order using the standard iterative approach.
#include <stdio.h>
// Function to perform insertion sort
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert key at correct position
}
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
insertionSort(arr, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}In this approach, the array is divided into a sorted and unsorted portion. Each element from the unsorted portion is compared with the sorted elements and inserted at the correct position. This ensures gradual building of a sorted array.
Program 2: Recursive Insertion Sort
This program demonstrates Insertion Sort implemented recursively, where each call sorts the first n-1 elements and inserts the last element at the correct position.
#include <stdio.h>
// Recursive insertion sort function
void insertionSortRecursive(int arr[], int n) {
if (n <= 1)
return; // Base case: single element is sorted
// Sort first n-1 elements
insertionSortRecursive(arr, n - 1);
// Insert nth element into sorted array
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
insertionSortRecursive(arr, size);
printf("Sorted array: ");
display(arr, size);
return 0;
}The recursive version reduces the problem size by sorting the first n-1 elements, then inserts the nth element at the correct position. This demonstrates how iteration can be transformed into recursion while maintaining the same sorting logic.
FAQs
Q1: What is the time complexity of Insertion Sort?
Worst and average case: O(n²), best case (already sorted): O(n).
Q2: Is Insertion Sort stable?
Yes, it preserves the relative order of equal elements.
Q3: When is Insertion Sort preferred?
It is preferred for small datasets or arrays that are nearly sorted.
Q4: Can Insertion Sort sort in descending order?
Yes, by changing the comparison to arr[j] < key in the loop.
Conclusion
Insertion Sort is a simple and intuitive sorting algorithm suitable for small or nearly sorted arrays. Both iterative and recursive approaches provide flexibility and help understand fundamental sorting techniques. Its stability makes it useful in scenarios where relative order must be maintained.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A well-regarded textbook covering core C concepts and key data structures, including sorting algorithms like insertion sort.
- Insertion Sort – GeeksforGeeks – Clear explanation of insertion sort in C, showing how each item is inserted into the sorted portion of the list.
- Insertion Sort – Programiz – Step-by-step guide with pseudocode, working principle, and complexity overview for multiple languages, including C.
- C Program for Insertion Sort – GeeksforGeeks – Example C implementation of insertion sort, with detailed walkthroughs for small lists.
- Exploring Time and Space Complexities of Insertion Sort – Programiz Blog – Analysis of best, average, and worst-case scenarios for insertion sort; highlights its O(n) best-case on nearly sorted data, and O(1) space use.
- Introduction to Recursion – GeeksforGeeks – Beginner-friendly explanation of recursion: base condition, logic breakdown, and examples like factorial.
- Recursion Basics – Tutorialspoint – Definition of recursion in programming, with a simple example of functions calling themselves and what constitutes a recursive function.
