Example: Bogo Sort Algorithm in C++

// Bogo Sort Algorithm
#include <iostream>  // For input/output operations
#include <vector>    // For dynamic arrays (std::vector)
#include <algorithm> // For std::is_sorted and std::shuffle
#include <random>    // For std::default_random_engine
#include <chrono>    // For seeding the random number generator
#include <numeric>   // Not strictly needed but useful for future
                     // algorithms, good habit for vector ops.

// Function to check if the vector is sorted
template <typename T>
bool isSorted(const std::vector<T>& arr) {
    // Step 1: Iterate through the vector from the second element
    for (size_t i = 1; i < arr.size(); ++i) {
        // Step 2: If any element is less than its predecessor, it's not sorted
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    // Step 3: If the loop completes, all elements are in order
    return true;
}

// Function to perform Bogo Sort
template <typename T>
void bogoSort(std::vector<T>& arr) {
    // Step 1: Create a random number generator engine
    // Use current time as seed to ensure different shuffles each run
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine rng(seed);

    // Step 2: Loop indefinitely until the array is sorted
    while (!isSorted(arr)) {
        // Step 3: Shuffle the elements of the array randomly
        std::shuffle(arr.begin(), arr.end(), rng);
    }
}

int main() {
    // Step 1: Initialize a small vector of integers to be sorted
    std::vector<int> numbers = {3, 1, 4, 2}; // Using 4 elements for demonstration

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

    // Step 3: Call the bogoSort function to sort the array
    std::cout << "Sorting using Bogo Sort..." << std::endl;
    bogoSort(numbers);

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

    return 0;
}