Thuật toán Bubble Sort là gì? Giải thích dễ hiểu kèm demo trực quan

Bài viết này giúp làm rõ ý tưởng của Bubble Sort, cách thuật toán hoạt động và kèm theo một demo trực quan bằng JavaScript để quan sát từng bước so sánh – đổi chỗ trên một mảng nhỏ.

Bubble Sort giải bài toán gì?

Bài toán cơ bản của Bubble Sort là:

• Cho một mảng các phần tử (thường là số).
• Cần sắp xếp mảng đó theo thứ tự tăng dần hoặc giảm dần.

Bubble Sort sẽ duyệt mảng nhiều lần, mỗi lần “đẩy” các phần tử lớn dần về cuối mảng (nếu sắp xếp tăng dần), giống như những “bong bóng” nổi dần lên trên mặt.

Ý tưởng chính của thuật toán Bubble Sort

Bubble Sort hoạt động theo nguyên tắc rất trực quan:

1. Duyệt qua mảng từ trái sang phải, so sánh từng cặp phần tử liền kề.
2. Nếu hai phần tử đang xét sai thứ tự (ví dụ: a[i] > a[i+1] khi sắp xếp tăng dần) thì đổi chỗ chúng.
3. Sau một lượt duyệt, phần tử lớn nhất sẽ “trôi” về cuối mảng.
4. Lặp lại quá trình trên cho phần còn lại của mảng (không cần đụng đến phần đã “ổn định” ở cuối).
5. Có thể dừng sớm nếu trong một lượt duyệt không có phép đổi chỗ nào → mảng đã được sắp xếp.

Một cách nhìn khác: mỗi vòng lặp ngoài tương đương với một “pass” qua mảng, và sau mỗi “pass”, ít nhất một phần tử lớn nhất trong phần chưa sắp xếp sẽ được đưa về đúng vị trí.

Ví dụ minh họa trên mảng nhỏ

Giả sử ta có mảng:

[5, 3, 8, 4, 2, 7]

Nếu sắp xếp tăng dần bằng Bubble Sort:

• So sánh 5 và 3 → đổi chỗ → [3, 5, 8, 4, 2, 7]
• So sánh 5 và 8 → đúng thứ tự → giữ nguyên
• So sánh 8 và 4 → đổi chỗ → [3, 5, 4, 8, 2, 7]
• So sánh 8 và 2 → đổi chỗ → [3, 5, 4, 2, 8, 7]
• So sánh 8 và 7 → đổi chỗ → [3, 5, 4, 2, 7, 8]

Sau “pass” đầu tiên, 8 đã nằm ở cuối mảng. Các “pass” tiếp theo tiếp tục tinh chỉnh đến khi mảng được sắp xếp hoàn toàn.

Demo Bubble Sort bằng JavaScript

Demo dưới đây minh họa trực quan cách Bubble Sort chạy trên mảng [5, 3, 8, 4, 2, 7]:

• Hiển thị mảng hiện tại dưới dạng các “ô” số.
• Tô màu hai phần tử đang được so sánh ở mỗi bước.
• Log lại từng bước so sánh và đổi chỗ.
• Hiển thị kết quả cuối cùng sau khi sắp xếp xong.

Phân tích đoạn code Bubble Sort

1. Khởi tạo mảng và chuẩn bị bước chạy

Đầu tiên, ta định nghĩa mảng ban đầu và một hàm để “ghi lại” các bước của thuật toán:

var originalArray = [5, 3, 8, 4, 2, 7];

function bubbleSortWithSteps(arr) {
    var a = arr.slice(); // copy mảng
    var n = a.length;
    var steps = [];

    for (var i = 0; i < n - 1; i++) {
        var swapped = false;
        for (var j = 0; j < n - 1 - i; j++) {
            // Bước so sánh
            steps.push({
                type: "compare",
                i: j,
                j: j + 1,
                array: a.slice()
            });

            if (a[j] > a[j + 1]) {
                // Đổi chỗ
                var temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                swapped = true;

                steps.push({
                    type: "swap",
                    i: j,
                    j: j + 1,
                    array: a.slice()
                });
            }
        }
        if (!swapped) break; // mảng đã sort, dừng sớm
    }

    return { steps: steps, sorted: a };
}

Mỗi bước được lưu lại với:

• type: so sánh (compare) hoặc đổi chỗ (swap).
• i, j: hai vị trí đang được xử lý.
• array: trạng thái mảng tại thời điểm đó.

2. Vẽ mảng và tô màu từng cặp phần tử

Để demo trực quan, ta dựng một hàm hiển thị mảng dưới dạng các ô:

function renderArray(container, arr, highlightA, highlightB) {
    container.innerHTML = "";
    arr.forEach(function(value, index) {
        var div = document.createElement("div");
        div.className = "bubble-cell";
        if (index === highlightA || index === highlightB) {
            div.className += " bubble-cell-active";
        }
        div.textContent = value;
        container.appendChild(div);
    });
}

Các ô đang được so sánh hoặc vừa đổi chỗ sẽ được thêm class đặc biệt để đổi màu nền.

3. Chạy từng bước với setTimeout

Sau khi có danh sách các bước, ta chạy lần lượt bằng setTimeout để tạo hiệu ứng “animation”:

var bubbleTimer = null;

function playSteps(steps, sortedArray) {
    var index = 0;
    bubbleLog.innerHTML = "";
    bubbleResult.textContent = "Đang chạy thuật toán...";
    
    function next() {
        if (index >= steps.length) {
            renderArray(bubbleArray, sortedArray, null, null);
            bubbleResult.innerHTML =
                'Mảng đã được sắp xếp: <strong>[' + sortedArray.join(", ") + ']</strong>';
            return;
        }

        var step = steps[index];
        var msg = "";

        if (step.type === "compare") {
            msg = "So sánh phần tử vị trí " + step.i + " và " + step.j +
                  " (" + step.array[step.i] + " và " + step.array[step.j] + ").";
        } else if (step.type === "swap") {
            msg = "Đổi chỗ " + step.array[step.j] + " và " + step.array[step.i] + ".";
        }

        renderArray(bubbleArray, step.array, step.i, step.j);

        var p = document.createElement("p");
        p.innerHTML = msg;
        bubbleLog.appendChild(p);
        bubbleLog.scrollTop = bubbleLog.scrollHeight;

        index++;
        bubbleTimer = setTimeout(next, 600);
    }

    next();
}

Mỗi bước:

• Cập nhật giao diện mảng hiện tại.
• Ghi log mô tả thao tác.
• Chuyển sang bước tiếp theo sau một khoảng thời gian nhỏ.

Khi nào nên dùng Bubble Sort?

Bubble Sort không phải là thuật toán tốt nhất về hiệu năng, nhưng rất hữu ích trong các trường hợp:

• Khi đang học nền tảng về thuật toán sắp xếp.
• Khi dữ liệu nhỏ, độ phức tạp không phải là vấn đề.
• Khi muốn demo trực quan cách sắp xếp hoạt động (so sánh – đổi chỗ).

Trong thực tế, với dữ liệu lớn, người ta thường dùng các thuật toán như Quick Sort, Merge Sort hoặc các thuật toán tối ưu hơn được cài đặt sẵn trong thư viện chuẩn.

Kết luận

Bubble Sort là một thuật toán sắp xếp đơn giản nhưng cực kỳ hữu ích để hiểu cơ chế hoạt động cơ bản của các thuật toán sort: lặp, so sánh, đổi chỗ và dừng sớm khi mảng đã được sắp xếp.

Với demo trực quan bằng JavaScript ở trên, từng lần so sánh và đổi chỗ đều được minh họa rõ ràng, giúp bạn “nhìn thấy” thuật toán chạy như thế nào thay vì chỉ đọc lý thuyết.

Từ Bubble Sort, bạn có thể dễ dàng bước tiếp sang các thuật toán sắp xếp nâng cao hơn như Selection Sort, Insertion Sort, Merge Sort hoặc Quick Sort.