Example: Odd-Even Sort Implementation in C++

// Odd-Even Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

void oddEvenSort(std::vector<int>& arr) {
    int n = arr.size();
    bool isSorted = false; // Flag to check if the array is sorted

    while (!isSorted) {
        isSorted = true; // Assume array is sorted until a swap occurs

        // Odd Phase: Compare and swap elements at odd indices (1, 3, 5...)
        for (int i = 1; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                std::swap(arr[i], arr[i+1]);
                isSorted = false; // A swap occurred, so array might not be sorted yet
            }
        }

        // Even Phase: Compare and swap elements at even indices (0, 2, 4...)
        for (int i = 0; i <= n - 2; i += 2) {
            if (arr[i] > arr[i+1]) {
                std::swap(arr[i], arr[i+1]);
                isSorted = false; // A swap occurred
            }
        }
    }
}

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

int main() {
    // Step 1: Initialize an unsorted vector
    std::vector<int> arr = {5, 2, 8, 1, 9, 4, 3, 7, 6};
    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Apply Odd-Even Sort
    oddEvenSort(arr);

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

    // Test with another array
    std::vector<int> arr2 = {10, -5, 0, 20, 15};
    std::cout << "Original array 2: ";
    printArray(arr2);
    oddEvenSort(arr2);
    std::cout << "Sorted array 2:   ";
    printArray(arr2);

    return 0;
}