C++ Program For Insertion Sort In Ascending Order

In this article, you will learn how to implement the insertion sort algorithm in C++ to arrange elements in ascending order. We will cover its core logic, provide a practical code example, and explain its operation step-by-step.

Problem Statement

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently for tasks like searching, merging, or presenting information in a readable format. The problem is to arrange an array or list of elements into a specific order, typically ascending or descending. For smaller datasets or nearly sorted arrays, algorithms like insertion sort offer a simple and effective solution.

Example

Imagine you have a hand of playing cards. When you pick up a new card, you insert it into its correct position among the cards you already hold, maintaining a sorted hand. Insertion sort works similarly:

• Unsorted Array: [5, 2, 8, 1, 9]
• Sorted Array: [1, 2, 5, 8, 9]

Background & Knowledge Prerequisites

To understand insertion sort, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types, and variable declaration.
• 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 comparisons.

No specific headers beyond iostream are generally required for a basic console-based implementation.

Use Cases

Insertion sort, despite its O(n^2) worst-case time complexity, has several practical applications:

• Small Datasets: It performs well for arrays with a small number of elements, where its simplicity outweighs the performance cost of more complex algorithms.
• Nearly Sorted Data: If an array is almost sorted, insertion sort is very efficient, as it requires only a few shifts per element.
• Online Sorting: It can sort a list as elements are received, one at a time, making it suitable for scenarios where data arrives sequentially and needs to be kept sorted.
• As a Subroutine: It's often used as a component in more advanced sorting algorithms, such as Timsort and Introsort, for sorting small partitions.
• Teaching/Learning: Its straightforward logic makes it an excellent algorithm for introductory computer science courses to illustrate basic sorting concepts.

Insertion Sort Algorithm

Insertion sort builds the final sorted array one item at a time. It iterates through the input array, taking one element from the unsorted part and inserting it into its correct position in the sorted part.

Approach Title: Iterative Insertion Sort

One-line summary: This method iteratively selects elements from the unsorted portion of the array and inserts them into their correct position within the already sorted portion.

// Insertion Sort in Ascending Order
#include <iostream>
#include <vector> // Using vector for dynamic array, but can be done with raw array

void insertionSort(std::vector<int>& arr) {
    // Step 1: Iterate through the array starting from the second element
    // The first element (index 0) is considered already sorted by itself
    for (int i = 1; i < arr.size(); ++i) {
        // Step 2: Store the current element to be inserted
        int key = arr[i];
        // Step 3: Initialize 'j' to the index of the last element in the sorted part
        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]; // Shift element to the right
            j = j - 1;           // Move to the left in the sorted part
        }
        // Step 5: Place the key element at its correct position
        arr[j + 1] = key;
    }
}

int main() {
    // Step 1: Define an unsorted array
    std::vector<int> numbers = {12, 11, 13, 5, 6};

    std::cout << "Original array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Step 2: Call the insertion sort function
    insertionSort(numbers);

    // Step 3: Print the sorted array
    std::cout << "Sorted array (ascending): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Sorted array (ascending): 5 6 11 12 13

Stepwise Explanation for Clarity:

1. Outer Loop (for (int i = 1; i < arr.size(); ++i)):

• This loop starts from the second element (i = 1) because the first element (arr[0]) is considered a sorted sub-array of one element.
• The variable i marks the beginning of the unsorted part of the array. Elements from 0 to i-1 are always sorted.

1. int key = arr[i];:

• key stores the current element that needs to be positioned correctly within the sorted part.

1. int j = i - 1;:

• j is an index that points to the last element of the sorted sub-array (arr[0...i-1]).

1. 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 decreases).
• Condition j >= 0: Ensures we don't go out of bounds of the array.
• Condition arr[j] > key: Checks if the element in the sorted part is greater than our key. If it is, key should be placed before arr[j].
• arr[j + 1] = arr[j];: If arr[j] is greater than key, it means arr[j] needs to be shifted one position to the right to make space for key.
• j = j - 1;: Move j one position to the left to compare key with the next element in the sorted sub-array.

1. 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.
• j + 1 is the index where key should be inserted.

This process continues until all elements have been moved from the unsorted part to their correct positions in the sorted part, resulting in a fully sorted array.

Conclusion

Insertion sort is an intuitive and easy-to-implement sorting algorithm, particularly efficient for small lists or arrays that are already mostly sorted. While its O(n^2) worst-case performance makes it less suitable for very large, unsorted datasets compared to algorithms like QuickSort or MergeSort, its stability and low overhead for specific use cases ensure its relevance in computer science.

Summary

• Concept: Builds a sorted array one element at a time by inserting each new element into its correct place in the already sorted portion.
• Best Use Cases: Small datasets, nearly sorted data, online sorting, and as a subroutine in hybrid sorting algorithms.
• Time Complexity:
• Best Case: O(n) (when the array is already sorted).
• Average/Worst Case: O(n^2).
• Space Complexity: O(1) (in-place sorting).
• Stability: It is a stable sorting algorithm, meaning elements with equal values maintain their relative order.