C Program For Insertion Sort In Array

Sorting data is a fundamental task in computer science, essential for optimizing search, merging, and other data processing operations. In this article, you will learn how to implement the Insertion Sort algorithm in C, understanding its mechanics and when to use it effectively.

Problem Statement

Efficiently organizing data is crucial for many applications, from database management to optimizing search operations. When dealing with smaller datasets or nearly sorted arrays, basic sorting algorithms offer a straightforward and often efficient solution. The challenge is to arrange an array of elements in a specific order (ascending or descending) using an intuitive and easy-to-implement method.

Example

Consider an unsorted array of integers: Original Array: [5, 2, 8, 1, 9]

After applying insertion sort, the array will be ordered as: Sorted Array: [1, 2, 5, 8, 9]

Background & Knowledge Prerequisites

To understand and implement Insertion Sort, you should have a basic grasp of:

• C Language Fundamentals: Variables, data types, and operators.
• Arrays: How to declare, initialize, and access elements in a C array.
• Loops: Familiarity with for and while loops for iteration.
• Conditional Statements: Basic if statements for comparison.

No special libraries or complex setups are required beyond a standard C compiler.

Use Cases or Case Studies

Insertion Sort, despite being a simple algorithm, finds its niche in several practical scenarios:

• Sorting a Hand of Cards: When you pick up cards one by one and insert them into their correct position in your hand, you're essentially performing an insertion sort.
• Small Data Sets: For arrays with a small number of elements (typically less than 10-20), insertion sort can be faster than more complex algorithms due to its low constant factors and simple implementation.
• Nearly Sorted Data: If an array is already mostly sorted, insertion sort performs exceptionally well because it requires very few shifts.
• As Part of Hybrid Sorting Algorithms: Advanced sorting algorithms like Timsort (used in Python and Java) and Introsort often use insertion sort for small partitions or nearly sorted runs to leverage its efficiency in those specific cases.
• Embedded Systems: Its simplicity and minimal memory overhead make it suitable for resource-constrained environments where complex algorithms might be too heavy.

Solution Approaches

The core idea of insertion sort is to build a sorted array one element at a time. It iterates through the input array and removes one element at a time, finding the correct position within the already sorted part of the array and inserting it there.

Insertion Sort Algorithm

This approach directly implements the described mechanism of taking an element and inserting it into its correct place in the sorted sub-array.

One-line summary: Iterates through an array, taking each element and inserting it into its proper position within the previously sorted part of the array.

Code Example:

// Insertion Sort
#include <stdio.h>

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

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    // Step 1: Iterate from the second element (index 1) to the end of the array
    for (int i = 1; i < n; i++) {
        // Step 2: Store the current element to be inserted
        int key = arr[i];
        // Step 3: Initialize j to the index of the element just before 'key'
        int j = i - 1;

        // Step 4: 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;
        }
        // Step 5: Place the key at its correct position in the sorted sub-array
        arr[j + 1] = key;

        printf("Pass %d: ", i);
        printArray(arr, n);
    }
}

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;
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Pass 1: 11 12 13 5 6 
Pass 2: 11 12 13 5 6 
Pass 3: 5 11 12 13 6 
Pass 4: 5 6 11 12 13 
Sorted array: 5 6 11 12 13

Stepwise Explanation for Clarity:

1. Outer Loop (for (int i = 1; i < n; i++)): This loop iterates from the second element (i = 1) up to the last element of the array. The first element (arr[0]) is considered to be already sorted in a sub-array of size 1.
2. key = arr[i]: In each iteration, the current element arr[i] is stored in a key variable. This key is the element we need to insert into its correct position within the sorted sub-array arr[0...i-1].
3. Inner Loop (while (j >= 0 && arr[j] > key)): This loop compares key with elements in the sorted sub-array, moving backward from arr[i-1] down to arr[0].

• If an element arr[j] is greater than key, it means key should be placed before arr[j]. So, arr[j] is shifted one position to the right (arr[j + 1] = arr[j]).
• The j index is decremented (j = j - 1) to continue comparing key with the next element in the sorted sub-array.

1. arr[j + 1] = key;: Once the while loop terminates, it means either j became less than 0 (the key is the smallest element so far) or an element arr[j] was found that is less than or equal to key. At this point, j + 1 is the correct position to insert the key.

Conclusion

Insertion Sort is a simple and intuitive sorting algorithm that efficiently arranges elements by building a sorted array one item at a time. While its time complexity (O(n^2)) makes it less suitable for very large datasets compared to more advanced algorithms like Merge Sort or Quick Sort, its advantages lie in its simplicity, efficiency for small arrays, and excellent performance on nearly sorted data. It is also an in-place algorithm, requiring minimal additional memory.

Summary

• Mechanism: Builds a final sorted array one item at a time.
• Time Complexity:
• Best Case: O(n) (when the array is already sorted).
• Average/Worst Case: O(n^2) (when the array is unsorted or reverse sorted).
• Space Complexity: O(1) (in-place sorting).
• Stability: It is a stable sorting algorithm (maintains the relative order of equal elements).
• Use Cases: Ideal for small datasets, nearly sorted arrays, and as a component within hybrid sorting algorithms.