C++ Program For Insertion Sort Algorithm In Data Structure

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In this article, you will learn how to implement the insertion sort algorithm in C++ and understand its step-by-step operation.

Problem Statement

Sorting data is a fundamental operation in computer science, crucial for efficient data retrieval, processing, and presentation. The challenge lies in organizing elements in a specific order (e.g., ascending or descending) to improve search performance, facilitate data analysis, and present information clearly. For instance, imagine a list of student scores or product prices that need to be ordered.

Example

Consider an unsorted array of numbers: [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 be familiar with:

• C++ Basic Syntax: Understanding variables, data types, and operators.
• Arrays: How to declare, initialize, and access elements in a C++ array.
• Loops (for and while): Iterating through arrays and controlling program flow.
• Functions: Defining and calling simple functions.

Use Cases or Case Studies

Insertion sort, despite its O(N^2) worst-case time complexity, is efficient and practical in several specific scenarios:

• Small Datasets: For arrays with a small number of elements (typically less than 15-20), insertion sort often outperforms more complex algorithms due to its low constant factors and in-place nature.
• Nearly Sorted Data: If an array is already mostly sorted with only a few elements out of place, insertion sort performs exceptionally well, approaching O(N) time complexity. This makes it suitable for incrementally sorting data where new elements are frequently added to an already sorted list.
• Online Algorithms: Insertion sort can process elements as they arrive, building a sorted list incrementally. This is useful in scenarios where data is streamed and needs to be kept sorted without processing the entire dataset at once.
• As a Subroutine in Hybrid Sorting Algorithms: Some advanced sorting algorithms, like Timsort (used in Python and Java), use insertion sort for sorting small partitions of data, leveraging its efficiency on smaller inputs.
• Educational Purposes: Its simplicity and intuitive approach make it an excellent algorithm for teaching fundamental sorting concepts.

Solution Approaches

We will focus on the standard implementation of the insertion sort algorithm.

Standard Insertion Sort Algorithm

This approach iterates through the array, taking one element at a time and inserting it into its correct position within the already sorted portion of the array.

Code Example

// C++ Insertion Sort Algorithm
#include <iostream>

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

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    // Iterate from the second element (index 1) to the end of the array
    for (int i = 1; i < n; i++) {
        // 'key' is the element to be inserted into the sorted subarray
        int key = arr[i];
        // 'j' is the index of the last element in the sorted subarray
        int j = i - 1;

        // 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 subarray
        }
        // Place 'key' at its correct position in the sorted subarray
        arr[j + 1] = key;
    }
}

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
    std::cout << "Original array: ";
    printArray(arr, n);

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

    // Step 4: Print the sorted array
    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 i = 1 to n-1): The algorithm starts by considering the second element (at index 1) as the first element to be inserted into the "sorted" portion of the array. The first element (at index 0) is inherently considered sorted.
2. Select Key: In each iteration of the outer loop, arr[i] is selected as the key. This key is the element that needs to be placed in its correct position within the arr[0...i-1] subarray, which is already sorted.
3. Inner Loop (while j >= 0 && arr[j] > key):

• A pointer j is initialized to i-1 (the last element of the sorted subarray).
• This loop compares key with elements in the sorted subarray, moving from right to left (j decreases).
• If an element arr[j] is greater than key, it is shifted one position to the right (arr[j+1] = arr[j]) to make space for key.
• This shifting continues as long as j is non-negative (within array bounds) and arr[j] is greater than key.

1. Insert Key: Once 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 inserted into the position j+1. This is its correct sorted position relative to the elements arr[0...i-1].
2. Repeat: The process repeats for the next element until the entire array has been traversed and all elements are in their correct sorted positions.

Conclusion

Insertion sort is a straightforward and intuitive sorting algorithm. It is particularly efficient for small datasets and nearly sorted arrays, making it a valuable tool in specific programming scenarios and an excellent algorithm for understanding basic sorting principles.

Summary

• Insertion sort builds a sorted array one element at a time.
• It works by taking an element from the unsorted part and inserting it into its correct position in the sorted part.
• Time Complexity: O(N^2) in the worst and average cases, but O(N) in the best case (when the array is already sorted).
• Space Complexity: O(1) as it is an in-place sorting algorithm.
• Advantages: Simple to implement, efficient for small arrays or nearly sorted data, and stable (maintains the relative order of equal elements).
• Disadvantages: Inefficient for large, randomly ordered datasets compared to algorithms like Merge Sort or Quick Sort.