Thuật toán QuickSort

Một chút lịch sử

Thuật toán chia để trị phổ biến nhất mà tất cả anh em lập trình đều được học qua thời mài đích trường đại học. Được tạo ra bởi Tony Hoare năm 1959

Trên là hình ông Tony Hoare trình làng thuật toán QuickSort năm 1960 tại Moscow.

Để mô tả thuật toán này, nó bao gồm các bước chính như sau:

1. Nếu chỉ còn một phần tử hoặc không còn phần tử nào để sort, nghĩa là KẾT THÚC
2. Mỗi lần gọi sort chúng ta chọn một phần tử làm CHỐT ĐỂ SO SÁNH
3. So sánh tất cả các phần tử còn lại với CHỐT ĐỂ SO SÁNH, nhỏ hơn đưa vào một nhóm nhỏ hơn, lớn hơn đưa qua nhóm lớn hơn
4. (Đệ quy) thực hiện đúng những bước đã làm với các phần tử thuộc 2 nhóm mới có

Độ phức tạp của nó là O(NlogN), trường hợp xấu nhất là O(N2). Đại khái nó là một trong những phương pháp sort mảng hiệu quả nhất.

Để hiểu độ phức tạp của thuật toán, các bạn đọc bài này

Hiện thực bằng Javascript

Trong javascript đã có sẵn hàm sort vậy tại sao chúng ta lại quan tâm tới thuật toán QuickSort?

let items = [5,3,7,6,2,9];
console.log(items.sort());
// [2, 3, 5, 6, 7, 9]

Hàm sort() của javascript sẽ tùy thuộc vào engine trình duyệt, insertion sort cho Chrome và merge sort cho Firefox và Safari

Nó không phù hợp khi phải sort số lượng dữ liệu lớn, hay là một mảng object, dạng [{order: 1}, {order: 4}, {order: 2}]

Hiện thực cho mảng bình thường, phần mảng là object các bạn chỉ cần thay điều kiện so sánh

function quickSort(unsortedArray = []) {
    let smaller = []; let larger = [];
    if (unsortedArray.length <= 1)
        return unsortedArray;
    
    for (var i = 1; i < unsortedArray.length; i++) { 
        if (unsortedArray[i] < unsortedArray[0])
            smaller.push(unsortedArray[i]); 
        if (unsortedArray[i] >= unsortedArray[0]) 
            larger.push(unsortedArray[i]); 
    }
    return quickSort(smaller).concat(unsortedArray[0], quickSort(larger));
}