Giải thuật là lấy ngẫu nhiên một phần tử (phần tử chốt) để chia nhỏ thành 2 mảng, gọi là mảng trái và phải. Sau đó so sánh từng phần tử của mảng trái, phải so với phần tử chốt. Trong trường hợp sắp xếp tăng dần thì so sánh tìm phần tử mảng trái lớn hơn phần tử chốt và tim phần tử mảng phải nhỏ hơn phần tử chốt và thực hiện hoán đổi cho nhau. Tại mốc phần tử được hoán đổi sẽ tiếp tục phân chia nhỏ mảng để tiếp tục sắp xếp.

Tiếp tục phân chia các mảng nhỏ và thực hiện cho tới khi các mảng con có độ dài bằng 1. 

Sau đây là mô phỏng thuật toán Quick Sort

Mã nguồn được thực hiện trên Javascript

var QuickSort = function ()
{
    $.extend(this, new SortX());

    this.onCreateScripts = function (array, scripts)
    {
        var $this = this;

        var addScript = function (a1, a2, action, left, right)
        {
            if (left) scripts.push({ run: function () { $this.getRow1().find(".fa-caret-down").remove(); a1.a.parent().append("<i class='fa fa-caret-down'></i>"); } });
            if (right) scripts.push({ run: function () { $this.getRow1().find(".fa-caret-up").remove(); a2.a.parent().append("<i class='fa fa-caret-up'></i>"); } });
            scripts.push($this.createScript0(a1, a2)); // Script lấy ra 2 số cần so sánh
            scripts.push($this.createScript1(a1, a2)); // Script để thực hiện so sánh giữa 2 số
            return action();
        }
        var addScriptLeftRight = function (left, right)
        {
            var script = {};
            script.run = function ()
            {                    
                $this.getRow1().find(".fa").remove();
                left.a.parent().append("<i class='fa fa-chevron-left'></i>");
                right.a.parent().append("<i class='fa fa-chevron-right'></i>");
            }
            scripts.push(script);
        }            

        var sort = function (left, right)
        {
            if (array.length == 0) return;
            if (left >= right) return;

            var middle = parseInt(left + (right - left) / 2);
            var pivot = array[middle];

            addScriptLeftRight(array[left], array[right]);
            scripts.push($this.createScriptPivot(pivot));                

            var i = left, j = right;

            while (i <= j)
            {
                while (addScript(array[i], pivot, () => array[i].number < pivot.number, true, false)) i++;
                while (addScript(pivot, array[j], () => array[j].number > pivot.number, false, true)) j--;                    

                if (i <= j)
                {
                    var a1 = array[i];
                    var a2 = array[j];

                    array[j] = a1;
                    array[i] = a2;

                    scripts.push($this.createScript2(a1, a2)); // Script thực hiện hoán đổi giữa 2 số với nhau.

                    i++;
                    j--;
                }
            }

            if (left < j) sort(left, j);
            if (right > i) sort(i, right);
        }

        // Bắt đầu thực hiện sắp xếp
        sort(0, array.length - 1);

        // Clear 2 vị trí đầu cuối ở mảng sắp xếp cuối cùng
        scripts.push({ run: function () { $this.getRow1().find(".fa").remove(); } });
    }
}

var pageSortX = new PageSortX();
pageSortX.sortX = new QuickSort();
pageSortX.start();

Phần tử chốt ảnh hưởng khá nhiều tới việc sắp xếp, trong đoạn code mô phỏng thì tôi lấy phần tử chốt là ở chính giữa. Tuy nhiên có thể chọn phần tử chốt là phần tử đầu, cuối của mảng.

Mô hình để thực hiện bài toán mô phỏng được là Strategy Pattern mà tôi đã chia sẻ ở bài viết Mô phỏng phép tính nhân 2 số bé hơn và gần bằng 100

Chúc các bạn một ngày cuối tuần vui vẻ

Sơn 20

Nếu bạn thấy nội dung chia sẻ này có ích với bạn hãy Donate để tạo động lực cho tôi viết các bài viết tiếp theo nhé. Cảm ơn nhiều !!!!