Mastering Insertion Sort: A Comprehensive Guide for Beginners

Introduction to Insertion Sort

Insertion sort is a simple and intuitive comparison-based sorting algorithm which is quite effective for small data sets and partially sorted lists. This blog post delves into the mechanics of insertion sort, offering a clear understanding through its algorithm, pseudo code, practical implementation in C, and an analysis of its time and space complexities. By the end of this post, you’ll have a solid grasp of where and how to use insertion sort efficiently.

Detailed Algorithm with Pseudo Code and Explanation

Insertion sort works similarly to the way you might sort playing cards in your hands. It builds the final sorted array (or list) one item at a time. It assumes that the first element is already sorted, then it moves to the next element, picks it up and places it into its correct position relative to the first element. This process is repeated until all elements are sorted.

Pseudo Code:

The pseudo code for insertion sort is as follows:

function insertionSort(array)
    for i from 1 to length(array) - 1
        current = array[i]
        j = i - 1
        
        // Find the correct position for the current element
        while j >= 0 and array[j] > current
            array[j + 1] = array[j]
            j = j - 1
        end while
        
        // Place the current element into its correct position
        array[j + 1] = current
    end for
end function

Explanation of Logic:

• Step 1: Start by assuming that the first element is sorted.
• Step 2: Move to the next element. This becomes your current element for comparison.
• Step 3: Compare the current element with the sorted elements. Search for the correct position of the current element by comparing it backward.
• Step 4: Shift elements to the right to create position for the new element.
• Step 5: Insert the current element into its correct position.
• Step 6: Repeat the process for each element in the list.

Implementation in C Language

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Explanation of the C Code:

• Function Definition: The insertionSort function iterates from the second element to the last element of the array.
• Key Element: The key variable holds the value of the element to be inserted.
• Correct Position: Elements in the sorted section that are greater than key are moved one position to the right to make room for the key.
• Inserting the Key: Once the correct position is found, key is placed in its correct location.

Time and Space Complexity:

• Time Complexity:
  • Best Case: O(n) when the array is already sorted.
  • Average and Worst Case: O(n²) due to nested loops.
• Space Complexity:
  • O(1) because it requires a single additional memory space for the key element.

Usage

Insertion sort is favored when the array is already partially sorted, when the data set is small, and in scenarios where simplicity is preferred over efficiency.

Conclusion

Despite its simplicity, insertion sort provides a great learning tool for understanding sorting mechanisms and serves as a stepping stone towards more complex algorithms like Quick Sort and Merge Sort. Its adaptive nature makes it useful in real-time data situations where data arrives in intervals.