C++ Program For Insertion Sort Using Function

In this article, you will learn how to implement the Insertion Sort algorithm in C++ using a dedicated function. This approach promotes code reusability and modularity, making your sorting logic clean and easy to manage.

Problem Statement

Efficiently arranging elements in a specific order (ascending or descending) is a fundamental task in computer science. Unsorted data makes searching, merging, and analysis difficult and slow. For smaller datasets, or nearly sorted arrays, a simple and efficient sorting algorithm like Insertion Sort is highly effective. The challenge is to implement this sorting logic as a reusable function.

Example

Consider an unsorted array of integers:

Unsorted Array: [12, 11, 13, 5, 6]

After applying Insertion Sort, the array will be sorted in ascending order:

Sorted Array: [5, 6, 11, 12, 13]

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C++ Fundamentals: Variables, data types, loops (for, while), conditional statements (if-else).
• Arrays: How to declare, initialize, and access elements in C++ arrays.
• Functions: How to define and call functions, pass parameters by value and reference.

No specific libraries beyond standard I/O are required for this implementation.

Use Cases or Case Studies

Insertion Sort, while not the fastest for large datasets, is useful in several specific scenarios:

• Small Datasets: For arrays with a small number of elements (e.g., less than 20-30), Insertion Sort performs very well due to its low constant factors and in-place nature.
• Nearly Sorted Data: If an array is already mostly sorted, Insertion Sort is highly efficient as it requires only a few shifts per element. Its time complexity approaches O(n) in this best-case scenario.
• Online Sorting: When elements are received incrementally and need to be kept sorted, Insertion Sort can efficiently insert each new element into its correct position without re-sorting the entire collection.
• Hybrid Sorting Algorithms: It's often used as part of more complex sorting algorithms (like Timsort and Introsort) to sort small partitions of data.
• Linked Lists: Because it involves frequent insertions and removals, Insertion Sort can be adapted efficiently for linked lists where element shifting is inexpensive.

Solution Approaches

We will implement Insertion Sort using an iterative approach encapsulated within a C++ function. This function will take an array and its size as input and sort the array in place.

Insertion Sort using a C++ Function

This approach defines a void function that takes an integer array and its size. It sorts the array in ascending order by iterating through the array and inserting each element into its correct position within the already sorted part of the array.

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

// Function to perform Insertion Sort on an array
void insertionSort(int arr[], int n) {
    // Step 1: Iterate from the second element (index 1) to the end of the array
    for (int i = 1; i < n; i++) {
        // Step 2: Store the current element to be inserted
        int key = arr[i];
        // Step 3: Initialize j to the element just before the key
        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 to compare with the next element
        }
        // Step 5: Place the key at its correct position in the sorted subarray
        arr[j + 1] = key;
    }
}

// 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;
}

int main() {
    // Step 1: Declare an unsorted integer array
    int arr[] = {12, 11, 13, 5, 6};
    // Step 2: Calculate the size of the array
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 3: Print the original array
    std::cout << "Original array: ";
    printArray(arr, n);

    // Step 4: Call the insertionSort function to sort the array
    insertionSort(arr, n);

    // Step 5: 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. insertionSort(int arr[], int n) function:

• This function takes an integer array arr and its n (size) as parameters.

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

• It starts from the second element (i = 1) because the first element (arr[0]) is considered to be already sorted in a subarray of size 1.
• In each iteration, arr[i] is the element to be inserted into the correct position within the sorted subarray arr[0...i-1].

1. int key = arr[i];:

• The value of the current element (arr[i]) is stored in a temporary variable key. This is important because elements might be shifted to the right, overwriting arr[i].

1. int j = i - 1;:

• A pointer j is initialized to point to the last element of the sorted subarray (arr[0...i-1]).

1. Inner Loop (while (j >= 0 && arr[j] > key)):

• This loop compares key with elements in the sorted subarray, moving backward from arr[j] to arr[0].
• Condition 1 (j >= 0): Ensures we don't go out of bounds on the left side of the array.
• Condition 2 (arr[j] > key): If an element arr[j] in the sorted subarray is greater than key, it means key should be placed before arr[j].
• arr[j + 1] = arr[j];: If arr[j] is greater than key, arr[j] is shifted one position to its right to make space for key.
• j = j - 1;: The pointer j is decremented to compare key with the next element to its left.

1. arr[j + 1] = key;:

• Once the inner 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].

Conclusion

Implementing Insertion Sort using a dedicated function in C++ provides a clean, modular, and reusable solution for sorting arrays. While not optimal for very large, unsorted datasets, its simplicity, efficiency for small or nearly sorted arrays, and in-place nature make it valuable in specific programming contexts. Understanding its mechanics helps build a solid foundation in algorithm design.

Summary

• Insertion Sort is an efficient sorting algorithm for small or nearly sorted datasets.
• It works by building a sorted array one element at a time, inserting each new element into its correct position.
• Encapsulating the sorting logic in a C++ function (e.g., insertionSort) enhances code reusability and maintainability.
• The function typically takes the array and its size as parameters.
• The algorithm involves an outer loop to pick elements and an inner loop to shift elements and find the correct insertion point.
• Insertion Sort is an in-place sorting algorithm, meaning it doesn't require extra space proportional to the input size.