Thuật toán Bogo Sort

Thuật toán Bogo Sort là một trong những thuật toán sắp xếp rất đơn giản nhưng không hiệu quả. Cách thức hoạt động của thuật toán này là ngẫu nhiên hoán đổi các phần tử trong dãy và kiểm tra xem dãy đã được sắp xếp chưa. Nếu chưa, tiếp tục ngẫu nhiên hoán đổi và kiểm tra cho đến khi dãy đã được sắp xếp.

Dưới đây là một đoạn mã minh họa của Bogo Sort bằng ngôn ngữ Javascript

function isSorted(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

function bogoSort(arr) {
    while (!isSorted(arr)) {
        shuffle(arr);
    }
    return arr;
}

// Example usage:
const unsortedArray = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log("Unsorted array:", unsortedArray);

const sortedArray = bogoSort(unsortedArray.slice());
console.log("Sorted array:", sortedArray);

Lưu ý rằng độ phức tạp của Bogo Sort là rất cao, với trung bình là O((n+1)!) (nếu n là số phần tử trong dãy). Việc sắp xếp mảng bằng cách ngẫu nhiên trộn lộn cho đến khi mảng đã sắp xếp một cách ngẫu nhiên có thể mất rất nhiều thời gian, đặc biệt là với các mảng lớn. Vì vậy, Bogo Sort không phải là một thuật toán hiệu quả trong thực tế và thường chỉ được sử dụng như một trò đùa hoặc ví dụ để minh họa sự không hiệu quả của một số thuật toán sắp xếp.