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

BogoSort (còn gọi Permutation Sort, Stupid Sort, Slow Sort) là thuật toán sắp xếp cực kỳ kém hiệu quả. Thuộc парадигма "sinh và kiểm tra" (generate and test). Liên tục tạo hoán vị ngẫu nhiên cho đến khi mảng được sắp xếp.

Thuật toán

bogoSort(array, n):
    while mảng chưa được sắp xếp:
        xáo trộn mảng
    end

Code ví dụ

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm> // cho std::shuffle
using namespace std;

bool isSorted(int arr[], int n) {
    for (int i = 1; i < n; i++)
        if (arr[i] < arr[i-1])
            return false;
    return true;
}

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

void bogoSort(int arr[], int n) {
    while (!isSorted(arr, n))
        shuffle(arr, n);
}

int main() {
    srand(time(0));
    int data[] = {54, 74, 98, 5, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data) / sizeof(data[0]);
    
    cout << "Day truoc sap xep: ";
    for(int x : data) cout << x << " ";
    cout << endl;
    
    bogoSort(data, n);
    
    cout << "Day sau sap xep: ";
    for(int x : data) cout << x << " ";
    cout << endl;
}

Kết quả (mẫu - kết quả khác nhau mỗi lần chạy)

Day truoc sap xep: 54 74 98 5 98 32 20 13 35 40
Day sau sap xep: 5 13 20 32 35 40 54 74 98 98

Độ phức tạp

• Thời gian trung bình: O((n+1)!) - cực kỳ chậm
• Thời gian tốt nhất: O(n) (may mắn sắp xếp ngay lần đầu)
• Không gian: O(1)
• Ổn định: Không

Cải tiến: Bogobogosort

Đệ quy BogoSort trên các tiền tố ngày càng lớn - còn chậm hơn!

Lưu ý

Không bao giờ dùng BogoSort trong thực tế. Chỉ dùng cho mục đích giáo dục, hài hước, hoặc benchmark độ kém hiệu quả.