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

Ý tưởng của Quick Sort dựa trên kỹ thuật chia để trị: chọn một phần tử làm pivot, phân chia mảng thành hai phần nhỏ hơn pivot và lớn hơn pivot, rồi đệ quy sắp xếp từng phần.

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

• 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.

Quick Sort đặc biệt hữu dụng khi dữ liệu lớn và cần tốc độ, nhưng vẫn giữ được cách triển khai tương đối đơn giản.

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

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

1. Chọn một phần tử làm pivot (thường là phần tử cuối, đầu hoặc giữa mảng con).
2. Partition (phân hoạch) mảng: đưa các phần tử nhỏ hơn pivot sang bên trái, lớn hơn pivot sang bên phải.
3. Sau khi partition, pivot nằm ở đúng vị trí cuối cùng của nó trong mảng đã sắp xếp.
4. Đệ quy áp dụng Quick Sort cho hai mảng con bên trái và bên phải pivot.

Về độ phức tạp:

• Trung bình: O(n log n)
• Tệ nhất (chọn pivot xấu): O(n²)

Ví dụ minh họa

Cho mảng:

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

Nếu chọn pivot là phần tử cuối (7):

• Partition: đưa các phần tử < 7 sang trái, >= 7 sang phải → [5,3,4,2,7,8]
• Pivot 7 đã đúng vị trí.
• Đệ quy sắp xếp phần bên trái [5,3,4,2] và bên phải [8].

Demo Quick Sort bằng JavaScript

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

• Tô màu phần tử pivot.
• Tô màu phần tử đang được so sánh với pivot.
• Log lại từng lần so sánh và đổi chỗ trong quá trình partition.
• Hiển thị mảng sau mỗi bước để dễ quan sát.

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

1. Ghi lại các bước chạy (partition + đệ quy)

function quickSortWithSteps(arr) {
    var a = arr.slice();
    var steps = [];

    function swap(i, j) {
        var temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    function quickSort(left, right) {
        if (left >= right) {
            steps.push({
                type: "segment_done",
                left: left,
                right: right,
                array: a.slice()
            });
            return;
        }

        var pivotIndex = right;
        var pivotValue = a[pivotIndex];
        var i = left - 1;

        steps.push({
            type: "partition_start",
            left: left,
            right: right,
            pivotIndex: pivotIndex,
            pivotValue: pivotValue,
            array: a.slice()
        });

        for (var j = left; j < right; j++) {
            steps.push({
                type: "compare",
                index: j,
                pivotIndex: pivotIndex,
                pivotValue: pivotValue,
                array: a.slice()
            });

            if (a[j] <= pivotValue) {
                i++;
                if (i !== j) {
                    swap(i, j);
                    steps.push({
                        type: "swap",
                        i: i,
                        j: j,
                        pivotIndex: pivotIndex,
                        pivotValue: pivotValue,
                        array: a.slice()
                    });
                }
            }
        }

        // Đưa pivot về đúng vị trí (i + 1)
        if (i + 1 !== pivotIndex) {
            swap(i + 1, pivotIndex);
            steps.push({
                type: "pivot_swap",
                newPivotIndex: i + 1,
                oldPivotIndex: pivotIndex,
                pivotValue: pivotValue,
                array: a.slice()
            });
            pivotIndex = i + 1;
        } else {
            steps.push({
                type: "pivot_fixed",
                pivotIndex: pivotIndex,
                pivotValue: pivotValue,
                array: a.slice()
            });
        }

        steps.push({
            type: "pivot_done",
            pivotIndex: pivotIndex,
            pivotValue: pivotValue,
            left: left,
            right: right,
            array: a.slice()
        });

        quickSort(left, pivotIndex - 1);
        quickSort(pivotIndex + 1, right);
    }

    quickSort(0, a.length - 1);

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

2. Vẽ mảng & highlight pivot / phần tử đang so sánh

function renderQuickArray(container, arr, opts) {
    opts = opts || {};
    var pivotIndex = opts.pivotIndex;
    var activeIndex = opts.activeIndex;
    var segLeft = opts.segLeft;
    var segRight = opts.segRight;

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

        if (segLeft != null && segRight != null && index >= segLeft && index <= segRight) {
            div.classList.add("quick-in-range");
        }

        if (index === pivotIndex) {
            div.classList.add("quick-pivot");
        }

        if (index === activeIndex) {
            div.classList.add("quick-active");
        }

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

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

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

    function next() {
        if (index >= steps.length) {
            renderQuickArray(quickArray, sortedArray, {});
            quickResult.innerHTML =
                "Mảng đã được sắp xếp: <strong>[" + sortedArray.join(", ") + "]</strong>";
            return;
        }

        var step = steps[index];
        var msg = "";
        var opts = {
            pivotIndex: null,
            activeIndex: null,
            segLeft: null,
            segRight: null
        };

        if (step.type === "partition_start") {
            msg =
                "Bắt đầu partition đoạn [" +
                step.left +
                ", " +
                step.right +
                "] với pivot = " +
                step.pivotValue +
                " (vị trí " +
                step.pivotIndex +
                ").";
            opts.pivotIndex = step.pivotIndex;
            opts.segLeft = step.left;
            opts.segRight = step.right;
        } else if (step.type === "compare") {
            msg =
                "So sánh phần tử tại vị trí " +
                step.index +
                " (giá trị " +
                step.array[step.index] +
                ") với pivot = " +
                step.pivotValue +
                ".";
            opts.pivotIndex = step.pivotIndex;
            opts.activeIndex = step.index;
            opts.segLeft = null;
            opts.segRight = null;
        } else if (step.type === "swap") {
            msg =
                "Đổi chỗ phần tử tại vị trí " +
                step.i +
                " và " +
                step.j +
                " để đưa phần tử nhỏ hơn pivot về bên trái.";
            opts.pivotIndex = step.pivotIndex;
        } else if (step.type === "pivot_swap") {
            msg =
                "Đưa pivot (giá trị " +
                step.pivotValue +
                ") từ vị trí " +
                step.oldPivotIndex +
                " về vị trí " +
                step.newPivotIndex +
                ", pivot đã ở đúng vị trí.";
            opts.pivotIndex = step.newPivotIndex;
        } else if (step.type === "pivot_fixed") {
            msg =
                "Pivot (giá trị " +
                step.pivotValue +
                ") đã ở đúng vị trí " +
                step.pivotIndex +
                ".";
            opts.pivotIndex = step.pivotIndex;
        } else if (step.type === "pivot_done") {
            msg =
                "Kết thúc partition đoạn [" +
                step.left +
                ", " +
                step.right +
                "], pivot = " +
                step.pivotValue +
                " cố định tại vị trí " +
                step.pivotIndex +
                ".";
            opts.pivotIndex = step.pivotIndex;
        } else if (step.type === "segment_done") {
            msg =
                "Đoạn [" +
                step.left +
                ", " +
                step.right +
                "] có kích thước ≤ 1, không cần sắp xếp.";
        }

        renderQuickArray(quickArray, step.array, opts);

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

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

    next();
}

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

• Khi cần thuật toán sắp xếp nhanh cho dữ liệu lớn.
• Khi chấp nhận trường hợp tệ nhất nhưng quan tâm nhiều tới hiệu năng trung bình.
• Khi muốn triển khai sắp xếp in-place (ít tốn bộ nhớ hơn Merge Sort).

Kết luận

Quick Sort là thuật toán sắp xếp “chủ lực” trong nhiều hệ thống thực tế. Hiểu rõ cách chọn pivot, cách partition và cách đệ quy trên các đoạn con giúp bạn nắm được tinh thần của nhiều thuật toán chia để trị khác.

Với demo trực quan, từng bước so sánh, đổi chỗ và cố định pivot đều được thể hiện rõ, giúp bạn dễ dàng hình dung cách thuật toán hoạt động phía sau.