Example: Optimized Bubble Sort Algorithm in C++

// Optimized Bubble Sort Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

void optimizedBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped; // Flag to check if any swap occurred in a pass

    // Outer loop for passes
    for (int i = 0; i < n - 1; ++i) {
        swapped = false; // Reset flag for each pass
        // Inner loop for comparisons and swaps
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true; // A swap occurred
            }
        }

        // If no two elements were swapped by inner loop, then array is sorted
        if (!swapped) {
            break;
        }
    }
}

int main() {
    std::vector<int> numbers1 = {5, 1, 4, 2, 8};
    std::vector<int> numbers2 = {1, 2, 3, 4, 5}; // Already sorted array

    std::cout << "Original array 1: ";
    printArray(numbers1);
    optimizedBubbleSort(numbers1);
    std::cout << "Sorted array 1 (Optimized Bubble Sort): ";
    printArray(numbers1);

    std::cout << "\nOriginal array 2: ";
    printArray(numbers2);
    optimizedBubbleSort(numbers2);
    std::cout << "Sorted array 2 (Optimized Bubble Sort): ";
    printArray(numbers2);

    return 0;
}