C++ Program Of Simple Insertion Sort Implementation Using Array In Ascending Order

Sorting data is a fundamental task in computer science, crucial for optimizing search operations, database management, and more. In this article, you will learn how to implement the simple Insertion Sort algorithm in C++ to arrange an array of elements in ascending order.

Problem Statement

Efficiently organizing a list of items is a common requirement in many applications. Given an unsorted array of numbers, the problem is to sort these numbers in ascending order using an in-place sorting algorithm like Insertion Sort. This algorithm is particularly useful for small datasets or when data is added incrementally to an already sorted list, as it maintains the sorted property of the array with each insertion.

Example

Consider an unsorted array: [5, 2, 4, 6, 1, 3]

The Insertion Sort algorithm will transform it step-by-step into a sorted array:

• Initial: [5, 2, 4, 6, 1, 3]
• After 2 is inserted: [2, 5, 4, 6, 1, 3]
• After 4 is inserted: [2, 4, 5, 6, 1, 3]
• After 6 is inserted: [2, 4, 5, 6, 1, 3]
• After 1 is inserted: [1, 2, 4, 5, 6, 3]
• After 3 is inserted: [1, 2, 3, 4, 5, 6]

The final sorted array is [1, 2, 3, 4, 5, 6].

Background & Knowledge Prerequisites

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

• C++ Variables and Data Types: How to declare and use integer variables.
• Arrays: How to declare, initialize, and access elements of an array.
• Loops (for and while): How to iterate over arrays and perform repetitive tasks.
• Functions: How to define and call functions in C++.

Use Cases or Case Studies

Insertion Sort, despite its O(N^2) worst-case time complexity, finds application in several specific scenarios:

• Sorting Small Arrays: For arrays with a small number of elements (e.g., fewer than 20-30), Insertion Sort can be more efficient than more complex algorithms due to its low constant factors and in-place nature.
• Nearly Sorted Data: If an array is already mostly sorted, Insertion Sort performs very well, approaching O(N) time complexity because fewer shifts are required.
• Online Algorithms: When data is received incrementally and needs to be kept sorted, Insertion Sort can efficiently insert new elements into their correct positions in the already sorted part of the array.
• As a Subroutine in Hybrid Sorts: Algorithms like Timsort (used in Python and Java) and Introsort use Insertion Sort for sorting small partitions of the array, leveraging its efficiency in such contexts.
• Linked Lists: Insertion sort can be implemented efficiently on linked lists since inserting an element in the middle of a linked list is a constant-time operation once the position is found.

Solution Approaches

C++ Implementation of Simple Insertion Sort

This approach sorts an array by iterating through it and, for each element, finding its correct position within the already sorted part of the array and inserting it there.

One-line summary: Iterate through the array, taking each element and inserting it into its correct position within the sorted subarray to its left.

Code Example:

// Simple Insertion Sort using Array
#include <iostream> // For input/output operations

// Function to perform insertion sort on an array
// arr[]: The array to be sorted
// n: The size of the array
void insertionSort(int arr[], int n) {
    // Loop through the array starting from the second element (index 1)
    // because the first element (index 0) is considered sorted by itself.
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Store the current element as 'key' to be inserted
        int j = i - 1;    // Initialize 'j' to the last element of the sorted subarray (to the left of key)

        // Move elements of arr[0...i-1], that are greater than key,
        // to one position ahead of their current position.
        // This creates space for the 'key'.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // Shift element arr[j] to the right
            j = j - 1;           // Move 'j' to the previous element in the sorted part
        }
        arr[j + 1] = key; // Place the 'key' in its correct sorted position
    }
}

// Function to print the elements of an 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: Declare and initialize an array
    int arr[] = {12, 11, 13, 5, 6};
    // Calculate the size of the array
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array to show its initial state
    std::cout << "Original array: ";
    printArray(arr, n);

    // Step 3: Call the insertionSort function to sort the array in ascending order
    insertionSort(arr, n);

    // Step 4: Print the sorted array to show the result
    std::cout << "Sorted array (ascending): ";
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

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

Stepwise Explanation:

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

• It takes an integer array arr and its size n as input.
• Outer for 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 its own subarray.
• int key = arr[i];: The current element arr[i] is stored in a temporary variable key. This key is what we need to insert into its correct position in the sorted part of the array (elements from arr[0] to arr[i-1]).
• int j = i - 1;: An index j is initialized to point to the last element of the sorted subarray.

1. Inner while loop (while (j >= 0 && arr[j] > key)): This loop compares key with elements in the sorted subarray (arr[0] to arr[j]) from right to left.

• j >= 0: Ensures that we don't go out of bounds of the array.
• arr[j] > key: Checks if the current element in the sorted subarray (arr[j]) is greater than our key. If it is, arr[j] needs to be shifted to the right to make space for key.
• arr[j + 1] = arr[j];: If arr[j] is greater than key, it is shifted one position to the right (arr[j+1]).
• j = j - 1;: The index j is decremented to move to the next element on the left in the sorted subarray, continuing the comparison.

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. The key is then inserted at arr[j + 1].

1. printArray(int arr[], int n) function: This utility function simply iterates through the array and prints its elements, separated by spaces.

1. main() function:

• An unsorted integer array arr is declared and initialized.
• The size n of the array is calculated.
• The original array is printed.
• insertionSort() is called to sort the array.
• The sorted array is then printed.

Conclusion

Insertion Sort is a straightforward and intuitive sorting algorithm that builds a final sorted array one item at a time. It shines for small datasets and nearly sorted arrays due to its adaptive nature and minimal overhead. Understanding its mechanism provides a strong foundation for delving into more complex sorting algorithms.

Summary

• Insertion Sort works by iteratively inserting an element from the unsorted part into its correct position in the already sorted part.
• It's an in-place sorting algorithm, meaning it requires minimal additional memory.
• Its time complexity is O(N^2) in the worst and average cases, making it less suitable for very large datasets.
• For small arrays or nearly sorted data, its performance can be comparable to or even better than more advanced algorithms due to lower constant factors.
• It is considered a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.