Chương trình C++ cho thuật toán BogoSort (Permutation Sort)

BogoSort là một thuật toán sắp xếp cực kỳ kém hiệu quả dựa trên hoán vị và tổ hợp, do đó còn được gọi là Permutation Sort. Nó còn có các tên gọi khác như: Shotgun Sort, Stupid Sort, Monkey Sort, hoặc Slow Sort. Thuật toán liên tục tạo ra các hoán vị của dữ liệu đầu vào cho đến khi tìm thấy một hoán vị đã được sắp xếp.

Ví dụ minh họa

Input: 5 3 4 2 1
Output: 1 2 3 4 5

Giải thích

Trong BogoSort, mảng chứa các phần tử chưa sắp xếp. Thuật toán kiểm tra xem các phần tử có theo thứ tự không; nếu không, nó hoán đổi ngẫu nhiên các phần tử và lặp lại quá trình cho đến khi mảng được sắp xếp.

Code ví dụ

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

bool isSorted(int *arr, int n) {
    while (--n >= 1) {
        if (arr[n] < arr[n-1]) {
            return false;
        }
    }
    return true;
}

void shuffle(int *arr, int n) {
    for(int i = 0; i < n; i++) {
        int temp = arr[i];
        int r = rand() % n;
        arr[i] = arr[r];
        arr[r] = temp;
    }
}

void bogosort(int *arr, int n) {
    while (!isSorted(arr, n)) {
        shuffle(arr, n);
    }
}

int main() {
    srand(time(0)); // Khởi tạo seed cho rand()
    int arr[] = {5, 3, 4, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bogosort(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "\t";
    }
    return 0;
}

Độ phức tạp

• Thời gian: O((n+1)!) - cực kỳ chậm, chỉ dùng cho mục đích giáo dục
• Không gian: O(1)
• Ổn định: Không

Lưu ý: BogoSort không bao giờ nên được sử dụng trong thực tế do độ phức tạp thời gian kinh khủng.