C Language Series

#131: Mastering Insertion Sort in C

Welcome back to the C Language Series! In this installment, #131, we're diving deep into another fundamental sorting algorithm: Insertion Sort. Often compared to how you might sort a hand of playing cards, Insertion Sort is intuitive, efficient for small datasets, and a great stepping stone to understanding more complex algorithms.

At its core, Insertion Sort builds the final sorted array (or list) one item at a time. It iterates through the input array and, for each element, it finds the correct position for that element within the already sorted part of the array, and inserts it there. The process continues until all elements have been processed.

How Insertion Sort Works: The Algorithm

Let's break down the logic of Insertion Sort step-by-step:

1. Start by considering the first element of the array as already sorted. This forms our "sorted subarray" of size 1.
2. Take the next element from the unsorted part of the array (let's call it the key).
3. Compare the key with elements in the sorted subarray, moving from right to left.
4. If an element in the sorted subarray is greater than the key, shift it one position to the right to make space.
5. Continue shifting elements until you find an element that is less than or equal to the key, or you reach the beginning of the array.
6. Insert the key into the vacant position.
7. Repeat steps 2-6 for all remaining elements in the unsorted part of the array.

Illustrative Example

Let's visualize the process with an example array: [12, 11, 13, 5, 6]

Initially, [12] is sorted. Unsorted: [11, 13, 5, 6]

• Pass 1: Element 11
  • The key is 11. Compare 11 with 12 (in the sorted part).
  • Since 11 < 12, shift 12 to the right. Array becomes: [_, 12, 13, 5, 6]
  • Insert 11 into the vacant position. Array: [11, 12, 13, 5, 6]
  • Sorted part: [11, 12]
• Pass 2: Element 13
  • The key is 13. Compare 13 with 12.
  • Since 13 > 12, no shifts are needed. The correct position is after 12.
  • Insert 13. Array: [11, 12, 13, 5, 6]
  • Sorted part: [11, 12, 13]
• Pass 3: Element 5
  • The key is 5. Compare 5 with 13. Since 5 < 13, shift 13. Array: [11, 12, _, 13, 6]
  • Compare 5 with 12. Since 5 < 12, shift 12. Array: [11, _, 12, 13, 6]
  • Compare 5 with 11. Since 5 < 11, shift 11. Array: [_, 11, 12, 13, 6]
  • Reached the beginning of the array. Insert 5. Array: [5, 11, 12, 13, 6]
  • Sorted part: [5, 11, 12, 13]
• Pass 4: Element 6
  • The key is 6. Compare 6 with 13. Since 6 < 13, shift 13. Array: [5, 11, 12, _, 13]
  • Compare 6 with 12. Since 6 < 12, shift 12. Array: [5, 11, _, 12, 13]
  • Compare 6 with 11. Since 6 < 11, shift 11. Array: [5, _, 11, 12, 13]
  • Compare 6 with 5. Since 6 > 5, stop shifting. The correct position is after 5.
  • Insert 6. Array: [5, 6, 11, 12, 13]
  • Sorted part: [5, 6, 11, 12, 13]

The array is now fully sorted: [5, 6, 11, 12, 13].

C Implementation of Insertion Sort

Here's how you can implement Insertion Sort in C:

#include <stdio.h>

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // Store the current element as key
        j = i - 1;     // Start comparing with the element just before the key

        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Place the key in its correct position
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test the algorithm
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Understanding the C Code

Let's break down the key parts of the insertionSort function:

• for (i = 1; i < n; i++): This outer loop iterates from the second element (index 1) to the last element of the array. The element at arr[i] is chosen as the key to be inserted into the sorted subarray arr[0...i-1].
• key = arr[i];: The current element from the unsorted portion is stored in a temporary variable key. This is crucial because elements might be shifted to the right, overwriting arr[i].
• j = i - 1;: The inner loop starts comparing key with elements in the sorted subarray, beginning from its rightmost element (which is arr[i-1], just before key).
• while (j >= 0 && arr[j] > key): This loop performs the shifting process.
  • j >= 0: Ensures we don't go out of bounds on the left side of the array (accessing negative indices).
  • arr[j] > key: Checks if the current element in the sorted subarray (arr[j]) is greater than our key. If it is, it means key should be placed before arr[j].
• arr[j + 1] = arr[j];: If arr[j] is greater than key, it is shifted one position to the right to make space for key.
• j = j - 1;: Moves to the previous element in the sorted subarray to continue comparisons.
• arr[j + 1] = key;: Once the while loop terminates (either key has found its spot because arr[j] is no longer greater, or we reached the beginning of the array), key is inserted into its correct sorted position. The position is j + 1 because the last element arr[j] that was greater than key has been shifted, or j became -1 indicating key is the smallest.

Time and Space Complexity Analysis

Understanding an algorithm's efficiency is key to choosing the right one for a given task.

• Time Complexity:
  • Worst Case: O(n²) - This occurs when the array is sorted in reverse order. For each element, the inner loop has to traverse and shift almost all elements in the sorted subarray.
  • Average Case: O(n²) - On average, for each element, roughly half of the elements in the sorted subarray need to be shifted.
  • Best Case: O(n) - When the array is already sorted. In this scenario, the inner while loop's condition (arr[j] > key) will almost always be false, resulting in minimal shifts and comparisons, making it linear.
• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm because it only requires a constant amount of extra memory (for the key variable and loop counters) regardless of the input array size.

Advantages and Disadvantages

Advantages:

• Simple Implementation: It's straightforward to understand and code.
• Efficient for Small Data Sets: Performs well when the number of elements is small.
• Adaptive: It is efficient for data sets that are already substantially sorted. The more sorted the input, the faster it runs (closer to O(n)).
• Stable: It preserves the relative order of elements with equal values.
• In-Place: Requires a minimal (O(1)) amount of additional memory space.
• Online Algorithm: It can sort a list as it receives it, as it processes elements one at a time.

Disadvantages:

• Inefficient for Large Data Sets: Its O(n²) average and worst-case time complexity make it impractical for sorting large arrays.
• Performance Degradation: Its performance significantly degrades with a large number of inversions (pairs of elements that are out of order).

When to Use Insertion Sort

Given its characteristics, Insertion Sort is a good choice in specific scenarios:

• Small Arrays: For arrays with a small number of elements (typically less than 10-20), Insertion Sort can be faster than more complex O(n log n) algorithms due to its low constant factors.
• Nearly Sorted Arrays: If you know or suspect that your data is already mostly sorted, Insertion Sort will perform exceptionally well, approaching O(n) time complexity.
• Online Sorting: When elements are received one by one and need to be kept sorted continuously.
• As part of Hybrid Sorting Algorithms: Many advanced sorting algorithms like Timsort (used in Python and Java) and Introsort switch to Insertion Sort for sorting small partitions of the array, leveraging its efficiency for small inputs.

Conclusion

Insertion Sort, while not the fastest for large, random datasets, holds a valuable place in the pantheon of sorting algorithms. Its simplicity, stability, and efficiency for specific use cases (especially small or nearly sorted data) make it an important concept for any C programmer to understand. It beautifully illustrates the idea of building a solution incrementally, a common pattern in computer science.

Stay tuned for the next installment in our C Language Series, where we'll explore even more powerful algorithms!