C++ Program For Insertion Sort In Array

In this article, you will learn how to implement the insertion sort algorithm in C++ to efficiently sort elements within an array. We will cover its mechanics, provide a practical code example, and discuss its applications.

Problem Statement

Sorting an array means arranging its elements in a specific order, typically ascending or descending. While various sorting algorithms exist, some are better suited for particular scenarios due to their simplicity, stability, or efficiency on small or partially sorted datasets. Insertion sort addresses the general problem of ordering elements by incrementally building a sorted portion of the array.

Example

Consider an unsorted array of integers: [12, 11, 13, 5, 6]. After applying insertion sort, the array will be sorted in ascending order: [5, 6, 11, 12, 13].

Background & Knowledge Prerequisites

To understand and implement insertion sort in C++, readers should have a basic understanding of:

• C++ Fundamentals: Variables, data types, basic input/output.
• Arrays: How to declare, initialize, and access elements in a one-dimensional array.
• Loops: for and while loops for iterating through array elements.
• Conditional Statements: if statements for comparisons.

Use Cases or Case Studies

Insertion sort is often preferred in specific scenarios:

• Small Datasets: It performs well on small arrays due to its low overhead and simplicity, often outperforming more complex algorithms like Quicksort for n < 10-20.
• Nearly Sorted Arrays: If an array is already mostly sorted, insertion sort is highly efficient, as it only needs to shift a few elements for each misplaced item.
• Online Sorting: When elements are received one by one and need to be kept sorted (e.g., maintaining a sorted list of scores as new scores come in), insertion sort can insert each new element into its correct position.
• As a Subroutine in Other Algorithms: It is sometimes used as a subroutine in more advanced hybrid sorting algorithms (like Timsort and Introsort) to sort small partitions of an array.
• Simple Implementation: Its straightforward logic makes it easy to understand and implement, suitable for educational purposes or when code simplicity is prioritized over raw performance for large datasets.

Solution Approaches

We will detail the standard iterative implementation of insertion sort.

1. Standard Iterative Insertion Sort

This is the most common and intuitive way to implement insertion sort. It builds the final sorted array (or list) one item at a time.

One-line summary: Iteratively takes an element from the unsorted part and inserts it into its correct position within the sorted part.

Code example:

// Insertion Sort in Array
#include <iostream>
#include <vector> // Using vector for dynamic array, but works with C-style arrays too

// Function to perform insertion sort on an array
void insertionSort(int arr[], int n) {
    // Start from the second element as the first element is considered sorted
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // The element to be inserted
        int j = i - 1;    // Index of the last element in the sorted part

        // 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]; // Shift element to the right
            j = j - 1;           // Move to the previous element in the sorted part
        }
        arr[j + 1] = key; // Place the key in its correct position
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

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

    std::cout << "Original array: ";
    printArray(arr, n);

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

    std::cout << "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. 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 a sorted sub-array of one element.
2. Select key: In each iteration, arr[i] is chosen as the key. This key is the element that needs to be inserted into its correct position within the already sorted portion of the array (elements from arr[0] to arr[i-1]).
3. Inner Loop (while (j >= 0 && arr[j] > key)): This loop compares key with elements in the sorted sub-array, moving from right to left (j = i - 1 down to 0).

• If an element arr[j] in the sorted sub-array is greater than key, it is shifted one position to the right (arr[j+1] = arr[j]).
• The index j is decremented (j = j - 1) to check the next element to the left in the sorted sub-array.

1. Insert key: When the while loop terminates (either j becomes negative, meaning key is the smallest, or arr[j] is less than or equal to key), the key is placed at arr[j+1]. This is its correct sorted position relative to the elements arr[0] through arr[i-1].
2. Repeat: The process continues for all subsequent elements, gradually building a fully sorted array.

Conclusion

Insertion sort is a simple and intuitive sorting algorithm that builds a sorted array one element at a time. It is particularly efficient for small datasets, arrays that are already nearly sorted, or in scenarios requiring online sorting. While its time complexity is O(n^2) in the worst and average cases, making it less suitable for very large, randomly ordered arrays compared to more advanced algorithms, its low overhead and stability make it a valuable tool in specific contexts.

Summary

• Concept: Builds a sorted sub-array by iteratively inserting elements from the unsorted part into their correct position.
• Time Complexity: O(n^2) in worst and average cases, O(n) in best case (nearly sorted array).
• Space Complexity: O(1) (in-place sorting).
• Stability: A stable sorting algorithm (maintains the relative order of equal elements).
• Use Cases: Ideal for small arrays, nearly sorted data, and online sorting.