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

Dù không nhanh bằng các thuật toán nâng cao như Quick Sort hay Merge Sort, Selection Sort lại rất hữu ích khi cần sự đơn giản, dễ cài đặt hoặc dùng để minh họa cách thức hoạt động của thuật toán sắp xếp.

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

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

• Cho một mảng các phần tử.
• Cần sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.

Selection Sort thực hiện điều đó bằng cách “chọn” phần tử nhỏ nhất và đưa nó về đầu phần chưa sắp xếp.

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

Selection Sort hoạt động theo các bước:

1. Chia mảng thành 2 phần: phần đã sắp xếp (ban đầu rỗng) và phần chưa sắp xếp.
2. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp.
3. Đổi chỗ nó với phần tử ở đầu phần chưa sắp xếp.
4. Mở rộng phần đã sắp xếp thêm 1 phần tử.
5. Lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Điểm thú vị: số lần đổi chỗ rất ít — mỗi vòng lặp ngoài chỉ có tối đa 1 lần swap.

Ví dụ minh họa

Cho mảng:

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

• Pass 1: tìm min trong [5,3,8,4,2,7] → min = 2 → đổi chỗ 2 ⇆ 5 → [2,3,8,4,5,7]
• Pass 2: tìm min trong [3,8,4,5,7] → min = 3 → giữ nguyên → [2,3,8,4,5,7]
• Pass 3: tìm min trong [8,4,5,7] → min = 4 → đổi chỗ 4 ⇆ 8 → …

Demo Selection Sort bằng JavaScript

Demo dưới đây minh họa từng bước:

• Tô màu phần tử đang được xem xét.
• Tô màu riêng phần tử đang là “nhỏ nhất hiện tại”.
• Swap khi kết thúc mỗi pass.
• Log từng bước.

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

1. Ghi lại các bước chạy

function selectionSortWithSteps(arr) {
    var a = arr.slice();
    var n = a.length;
    var steps = [];

    for (var i = 0; i < n - 1; i++) {
        var minIndex = i;

        for (var j = i + 1; j < n; j++) {
            // Đánh dấu bước đang so sánh
            steps.push({
                type: "compare",
                i: j,
                minIndex: minIndex,
                array: a.slice()
            });

            if (a[j] < a[minIndex]) {
                minIndex = j;

                // Cập nhật minIndex mới
                steps.push({
                    type: "newMin",
                    i: j,
                    minIndex: minIndex,
                    array: a.slice()
                });
            }
        }

        // Nếu minIndex thay đổi thì swap
        if (minIndex !== i) {
            var temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;

            steps.push({
                type: "swap",
                i: i,
                j: minIndex,
                array: a.slice()
            });
        }
    }

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

2. Vẽ mảng & highlight phần tử

function renderSelectionArray(container, arr, active, minIndex) {
    container.innerHTML = "";
    arr.forEach(function(value, index) {
        var div = document.createElement("div");
        div.className = "sel-cell";

        if (index === minIndex) div.classList.add("sel-min");
        if (index === active) div.classList.add("sel-active");

        div.textContent = value;
        container.appendChild(div);
    });
}

3. Chạy animation từng bước

function playSelectionSteps(steps, sortedArray) {
    var index = 0;
    selectionLog.innerHTML = "";
    selectionResult.textContent = "Đang chạy thuật toán...";

    function next() {
        if (index >= steps.length) {
            renderSelectionArray(selectionArray, sortedArray, null, null);
            selectionResult.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ử " + step.i + " với minIndex hiện tại (" + step.minIndex + ").";
        } else if (step.type === "newMin") {
            msg = "Cập nhật minIndex mới: " + step.minIndex + ".";
        } else if (step.type === "swap") {
            msg = "Đổi chỗ phần tử vị trí " + step.i + " và " + step.j + ".";
        }

        renderSelectionArray(selectionArray, step.array, step.i, step.minIndex);

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

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

    next();
}

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

• Dữ liệu nhỏ hoặc trung bình.
• Khi cần thuật toán đơn giản, dễ viết, dễ mô phỏng.
• Khi muốn giảm số lần swap (Selection Sort swap rất ít).

Kết luận

Selection Sort là thuật toán đơn giản nhưng rất hiệu quả để học cách hoạt động của cơ chế chọn phần tử nhỏ nhất. Với demo trực quan, từng bước tìm minIndex, so sánh và đổi chỗ đều được hiển thị rõ ràng, giúp bạn hiểu sâu cách thuật toán vận hành.