Quick Sort (Sắp xếp nhanh)

I. Giới thiệu

1. Tại sao nên "chơi cùng" với Quick Sort

2. Kỹ thuật chọn phần tử chốt

3. Ý tưởng cho Quick Sort

4. Miêu tả thuật toán

Xét một dãy số như sau:

Yêu cầu là sắp xếp dãy trên theo thứ tự không giảm từ trái qua phải.

Selection Sort

Chọn pivot là 6, xét 2 "quân lính" là A và B lần lượt đặt ở 2 đầu của dãy số (A ở vị trí đầu bên trái và B ở cuối bên phải).

Luật hành quân như sau:

2. Code

        const quickSort = (arr) => {
            if(arr.length <= 1) {
                return arr;
            }

            let pivot = arr[0];
            let leftArr = [];
            let rightArr = [];

            for(let i = 1; i < arr.length; i++) {
                if(arr[i] < pivot) {
                    leftArr.push(arr[i]);
                } else {
                    rightArr.push(arr[i]);
                }
            }

            return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
        }
        
        const arr = [3, 1, 4, 2, 5];
        console.log("Array: ", arr);
        
        const sortedArr = selectionSort(arr);
        console.log("Array after sorted: ", sortedArr);

Output:

3. Kết Luận

References