Example: Comb Sort on Array of Integers in C++

// Comb Sort on Array of Integers
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Function to perform Comb Sort
void combSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Initialize gap
    int gap = n;
    
    // Initialize swapped flag for the outer loop (to check if any swaps happened)
    bool swapped = true;

    // Loop until gap becomes 1 and no more swaps occur
    while (gap != 1 || swapped == true) {
        // Update gap for the next pass
        // A common shrink factor is 1.3
        gap = (int)(gap / 1.3);
        if (gap < 1) {
            gap = 1; // Ensure gap is at least 1
        }
        
        swapped = false; // Reset swapped flag for this pass
        
        // Perform a "bubble sort" pass with the current gap
        for (int i = 0; i < n - gap; ++i) {
            if (arr[i] > arr[i + gap]) {
                std::swap(arr[i], arr[i + gap]);
                swapped = true; // Indicate that a swap occurred
            }
        }
    }
}

int main() {
    // Step 1: Define an array of integers to be sorted
    std::vector<int> numbers = {8, 4, 1, 5, 9, 2, 7, 3, 6};

    // Step 2: Print the original array
    std::cout << "Original array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Step 3: Call the combSort function to sort the array
    combSort(numbers);

    // Step 4: Print the sorted array
    std::cout << "Sorted array (Comb Sort): ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}