Program Structure

The insertion sort algorithm sorts an array by building a sorted portion of the array one element at a time. It works by iterating through the array, taking one element from the unsorted portion, and placing it in the correct position in the sorted portion.

Code Explanation

The following C++ program implements the insertion sort algorithm:

#include <iostream>

using namespace std;

/**
 * Function to perform insertion sort on an array.
 * 
 * @param arr The array to be sorted.
 * @param n The number of elements in the array.
 */
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        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];
            j--;
        }
        arr[j + 1] = key;
    }
}

/**
 * Function to print the elements of an array.
 * 
 * @param arr The array to be printed.
 * @param n The number of elements in the array.
 */
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

/**
 * Main function to demonstrate insertion sort.
 */
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: ";
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}

Documentation

Function Descriptions

• void insertionSort(int arr[], int n): Sorts the array arr of size n using the insertion sort algorithm.
• void printArray(int arr[], int n): Prints the elements of the array arr of size n.

Main Function

The main function initializes an array, prints the unsorted array, calls the insertionSort function to sort the array, and then prints the sorted array.

Conclusion

The insertion sort algorithm is simple and efficient for small datasets. Its performance deteriorates with larger datasets but is useful in situations where data is mostly sorted.