Thuật toán Bubble Sort Triển khai và phân tích hiệu suất

Bubble Sort là một thuật toán sắp xếp đơn giản. Ý tưởng của Bubble Sort là lặp qua danh sách, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng ở sai thứ tự. Quá trình này tiếp tục cho đến khi không còn hoán đổi nào xảy ra.

Dưới đây là cách triển khai Bubble Sort trong JavaScript:

function bubbleSort(arr) {
    let n = arr.length;
    let swapped;

    do {
        swapped = false;
        for (let i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                // Hoán đổi arr[i - 1] và arr[i]
                let temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;

                swapped = true;
            }
        }
        // Giảm dần giá trị của n vì phần tử cuối cùng sau mỗi vòng lặp đã ở đúng vị trí
        n--;
    } while (swapped);

    return arr;
}

// Ví dụ sử dụng:
let array = [64, 34, 25, 12, 22, 11, 90];
console.log("Mảng ban đầu: " + array);
let sortedArray = bubbleSort(array);
console.log("Mảng sau khi sắp xếp: " + sortedArray);

Giải thích:

1. Khởi tạo:

   • n là độ dài của mảng.
   • swapped là biến cờ hiệu để theo dõi nếu có sự hoán đổi nào xảy ra trong vòng lặp.

2. Vòng lặp do-while:

   • Vòng lặp ngoài sử dụng cấu trúc do-while để đảm bảo rằng ít nhất một vòng lặp được thực hiện và tiếp tục cho đến khi không còn hoán đổi nào xảy ra.

3. Vòng lặp for:

   • Duyệt qua mảng từ phần tử thứ hai đến phần tử cuối cùng.
   • So sánh từng cặp phần tử liền kề, nếu phần tử trước lớn hơn phần tử sau thì hoán đổi chúng.

4. Giảm giá trị n:

   • Sau mỗi vòng lặp, giá trị của n giảm dần vì phần tử cuối cùng đã ở đúng vị trí và không cần kiểm tra nữa.

5. Trả về mảng đã sắp xếp:

   • Trả về mảng sau khi tất cả các phần tử đã được sắp xếp.

Thời gian và không gian:

• Thời gian: O(n^2) trong trường hợp xấu nhất và trung bình.
• Không gian: O(1) vì sắp xếp được thực hiện tại chỗ, không sử dụng thêm không gian bộ nhớ.

Bubble Sort đơn giản và dễ hiểu, nhưng không phải là thuật toán sắp xếp hiệu quả nhất đối với mảng lớn.