C++ Program For Insertion Sort Without Using Function

Insertion sort is a simple, efficient sorting algorithm for small datasets. It builds the final sorted array one item at a time by taking elements from the input array and inserting them into their correct position in a sorted subarray. In this article, you will learn how to implement the insertion sort algorithm in C++ directly within the main function, without using any custom helper functions.

Problem Statement

The challenge is to sort an array of integers in ascending order using the insertion sort algorithm. Specifically, the implementation must be entirely self-contained within the main function, meaning no separate user-defined functions for sorting or utility operations like printing the array. This approach is common in competitive programming or scenarios where minimizing function call overhead is critical, or when simply demonstrating algorithmic logic in its most basic form.

Example

Consider an unsorted array: [12, 11, 13, 5, 6]

After applying insertion sort, the array will be sorted as: [5, 6, 11, 12, 13]

Background & Knowledge Prerequisites

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

• C++ syntax: Variables, data types, and basic input/output.
• Arrays: How to declare, initialize, and access elements of an array.
• Loops: Especially for loops, which are fundamental for iterating through arrays.
• Conditional statements: if statements for comparisons.

Use Cases

Insertion sort, despite its quadratic time complexity (O(n²)) in the worst and average cases, is practical in several scenarios:

• Small datasets: It performs very well for small arrays due to its low constant factor.
• Nearly sorted arrays: If an array is almost sorted, insertion sort runs in linear time (O(n)), making it highly efficient.
• Online sorting: It can sort a list as it receives new elements.
• As a subroutine: Used as part of more complex algorithms, such as hybrid sorting algorithms (e.g., Timsort and Introsort) where it sorts small partitions.
• Educational purposes: Its simple logic makes it a great algorithm for understanding basic sorting concepts.

Solution Approaches

We will focus on a single, direct approach: implementing insertion sort entirely within the main function.

Insertion Sort within main()

Directly implement the insertion sort algorithm inside the main function using nested loops to handle the sorting logic.

// Insertion Sort without Function
#include <iostream>
#include <vector> // Using vector for dynamic array, can also use fixed-size array
using namespace std;

int main() {
    // Step 1: Initialize an array of integers
    vector<int> arr = {12, 11, 13, 5, 6};
    int n = arr.size();

    cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Step 2: Implement the Insertion Sort algorithm
    // Outer loop iterates from the second element (index 1) to the end of the array
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Store the current element to be inserted
        int j = i - 1;    // Initialize j to the last element of the sorted subarray

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

    // Step 3: Print the sorted array
    cout << "Sorted array:   ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Run

Sample Output

Original array: 12 11 13 5 6 
Sorted array:   5 6 11 12 13

Stepwise Explanation for Clarity

1. Array Initialization: An std::vector named arr is initialized with unsorted integer values. Its size n is also determined.
2. Original Array Display: A for loop is used to iterate through arr and print its contents, showing the state before sorting.
3. Outer Loop (for (int i = 1; i < n; i++)):

• This loop starts from the second element (i = 1) because the first element (arr[0]) is considered trivially sorted in a subarray of size one.
• key = arr[i]; stores the current element that needs to be inserted into its correct position within the sorted subarray arr[0...i-1].
• j = i - 1; initializes an index j to point to the last element of the already sorted portion of the array.

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

• This loop compares key with elements in the sorted subarray (arr[0...j]).
• It continues as long as j is a valid index (not less than 0) and the element at arr[j] is greater than key.
• arr[j + 1] = arr[j]; shifts elements to the right to make space for key. If arr[j] is larger than key, it needs to move one position to the right.
• j = j - 1; decrements j to compare key with the next element to its left.

1. Placement of key: Once the inner while loop terminates (either j becomes negative or arr[j] is less than or equal to key), the correct position for key is found.

• arr[j + 1] = key; inserts key into its sorted position.

1. Sorted Array Display: Another for loop prints the arr after the sorting process is complete, showcasing the sorted result.

Conclusion

Implementing insertion sort without using separate functions, directly within main, demonstrates a fundamental understanding of the algorithm's mechanics. This approach, while less modular for larger programs, effectively showcases how each element is picked and placed into its correct position within an expanding sorted subarray using simple loop and comparison structures. It's an excellent method for visualizing and grasping the core logic of this in-place sorting algorithm.

Summary

• Algorithm Basics: Insertion sort builds a sorted array one element at a time.
• In-Place Sort: It sorts the array without requiring extra space beyond a few temporary variables.
• main Function Implementation: The entire sorting logic can be contained within the main function using nested for and while loops.
• Key Logic: An outer loop picks elements, and an inner while loop shifts larger elements to the right to create space for the current element.
• Efficiency: Best for small datasets or nearly sorted arrays; has O(n²) worst-case time complexity.