Example: Shell Sort Implementation in C++ in C++

// Shell Sort Implementation in C++
#include <iostream>
#include <vector> // Using vector for dynamic arrays, common in modern C++
#include <numeric> // For std::iota if needed, not strictly for this simple example

// Function to print the elements of an array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Function to perform Shell Sort
void shellSort(std::vector<int>& arr) {
    int n = arr.size();

    // Start with a large gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is gap sorted
        for (int i = gap; i < n; i++) {
            // Store a[i] in temp and make a hole at position i
            int temp = arr[i];

            // Shift earlier gap-sorted elements up until the correct location for a[i] is found
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            // Put temp (the original a[i]) in its correct location
            arr[j] = temp;
        }
    }
}

int main() {
    // Step 1: Initialize an unsorted array
    std::vector<int> arr = {12, 34, 54, 2, 3};
    
    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(arr);

    // Step 3: Call the shellSort function to sort the array
    shellSort(arr);

    // Step 4: Print the sorted array
    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}