C Program For Insertion Sort Algorithm In Data Structure

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. In this article, you will learn how to implement the insertion sort algorithm in C.

Problem Statement

Sorting is a fundamental problem in computer science, requiring the arrangement of items in a list into a specific order (e.g., ascending or descending). Efficiently sorting data is crucial for various applications, from database management and search algorithms to data analysis and visualization. The challenge lies in finding an algorithm that can sort data effectively, considering factors like time complexity, space complexity, and stability for different dataset sizes and characteristics.

Example

Consider an unsorted array of integers: [12, 11, 13, 5, 6]

After applying the Insertion Sort algorithm, the array will be sorted in ascending order: [5, 6, 11, 12, 13]

Background & Knowledge Prerequisites

To understand and implement Insertion Sort in C, you should have a basic understanding of:

• C Programming Basics: Variables, data types, operators.
• Arrays: How to declare, initialize, and access elements in a C array.
• Loops: for and while loops for iterating through arrays.
• Conditional Statements: if statements for comparison logic.

Use Cases

Insertion Sort, despite its quadratic time complexity in the worst case, finds practical use in several scenarios:

• Small Datasets: It performs well and is simple to implement for sorting arrays with a small number of elements (typically less than 10-20).
• Nearly Sorted Arrays: If an array is already mostly sorted, Insertion Sort can be very efficient, as it only needs to perform a few shifts. Its time complexity approaches O(n) in this best-case scenario.
• Online Algorithms: It can sort a list as it receives new elements. Each new element is simply inserted into its correct position within the already sorted part of the list.
• Implementation Simplicity: Its straightforward logic makes it easy to understand and debug, suitable for educational purposes or when code simplicity is prioritized over raw performance on very large datasets.
• As a Subroutine in Hybrid Algorithms: Some sophisticated sorting algorithms, like Timsort (used in Python and Java), use Insertion Sort as a subroutine for sorting small partitions of data, leveraging its efficiency on small inputs.

Solution Approaches

Insertion Sort Algorithm

Insertion sort works by iterating through an array and, for each element, comparing it with the elements in the sorted portion of the array (which initially contains only the first element). If an element is smaller than one in the sorted part, it shifts larger elements to the right to make space and inserts the element into its correct position.

// Insertion Sort Algorithm
#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // Current element to be inserted
        j = i - 1;   // Start comparing with the element before the current one

        // 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 key at its correct position
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Define an unsorted array
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Apply insertion sort
    insertionSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13

Stepwise Explanation:

1. insertionSort(int arr[], int n) function:

• for (i = 1; i < n; i++): This outer loop iterates from the second element (i = 1) to the last element of the array. The first element (arr[0]) is considered already sorted.
• key = arr[i]: The current element arr[i] is stored in key. This is the element we need to insert into its correct position within the sorted subarray arr[0...i-1].
• j = i - 1: j is initialized to point to the last element of the sorted subarray.
• while (j >= 0 && arr[j] > key): This inner while loop compares key with elements in the sorted subarray (arr[0...j]) from right to left.
• If arr[j] (an element in the sorted subarray) is greater than key, it means arr[j] is in the wrong place and needs to be shifted one position to the right to make space for key.
• arr[j + 1] = arr[j]: The element arr[j] is shifted to arr[j + 1].
• j = j - 1: j is decremented to compare key with the next element to its left.
• arr[j + 1] = key: Once the while loop terminates (either j becomes negative or arr[j] is less than or equal to key), it means the correct position for key has been found. key is then inserted at arr[j + 1].

1. main function:

• An example array arr is initialized.
• The size n of the array is calculated.
• The original array is printed using printArray.
• The insertionSort function is called to sort the array.
• The sorted array is printed, demonstrating the algorithm's effect.

Conclusion

Insertion Sort is an intuitive and straightforward sorting algorithm. It builds a sorted array by repeatedly inserting elements from the unsorted part into their correct position in the sorted part. While its average and worst-case time complexity of O(n^2) makes it less suitable for very large datasets, its simplicity, stability, and efficiency for small or nearly sorted arrays make it a valuable algorithm to understand and a useful component in hybrid sorting approaches.

Summary

• Algorithm Type: Comparison-based sorting algorithm.
• Mechanism: Builds a sorted subarray one element at a time by repeatedly inserting elements into their correct position.
• Time Complexity:
• Worst-Case: O(n^2) (e.g., reverse sorted array).
• Average-Case: O(n^2).
• Best-Case: O(n) (e.g., already sorted array).
• Space Complexity: O(1) (in-place sorting).
• Stability: Stable (maintains the relative order of equal elements).
• Ideal Use Cases: Small arrays, nearly sorted arrays, online sorting, as a subroutine in other algorithms.