Categories Thuật toán

Thuật toán sắp xếp nhanh (quick sort), giải thích kèm ví dụ trong PHP [serial về các thuật toán cơ bản trong lập trình]

Sắp xếp nhanh

Tên nghe đã thấy hấp dẫn rồi đúng không các bạn, dân lập trình nói rằng, trên các mảng ngẫu nhiên và có số lượng tương đối, quick sort có tốc độ sắp xếp tốt hơn đáng kể so với bubble sort (sắp xếp nổi bọt) và tương đương merge sort (sắp xếp trộn), cụ thể số bước cần thiết của quick sort để sắp xếp hoàn thành yêu cầu là ít hơn [độ phức tạp của thuật toán là O(n log n)]. Giờ chúng ta sẽ cùng tìm hiểu xem nó như thế nào nhé.

Bài toán, cho dãy số: 4, 2, 9, 7, 3, 1, 6, 8, 10, 5

Hãy sắp xếp nó theo thứ tự từ nhỏ đến lớn.

Đây là đoạn mã mẫu PHP sử dụng ý tưởng về quick sort:

<?php
function kc_quickSort($arr) {
    if (count($arr) <= 1) return $arr;
    
    $pivot = $arr[0];
    $left = $right = array();
    
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    $left = kc_quickSort($left);
    $right = kc_quickSort($right);
    return array_merge($left, array($pivot), $right);
}

$arr = array(4, 2, 9, 7, 3, 1, 6, 8, 10, 5);
$arr = kc_quickSort($arr);

// hiển thị kết quả
print_r($arr);

Rất ngắn gọn đúng không các bạn, nhưng không dễ để hiểu. Điểm khác biệt lớn nhất với bubble sort ở đây là quick sort sử dụng kỹ thuật đệ quy, một kỹ thuật trong lập trình mà một hàm sẽ gọi lại chính bản thân nó để giải quyết các vấn đề con của chính nó cho đến khi vấn đề được giải quyết xong.

Trời ơi, vậy đệ quy là cái gì vậy?

Chúng ta cần một ví dụ đơn giản về đệ quy trong PHP, chẳng hạn đây là hàm tính giai thừa sử dụng đệ quy:

function factorial($n){
    if($n == 0){
        return 1;
    }
    else{
        return $n * factorial($n-1);
    }
}

echo factorial(6); // Output: 720

Chúng ta xem nó nói gì:

  • Nếu n = 0 thì trả về kết quả 1 và không làm gì nữa;
  • Nếu n khác 1 thì trả về n * factorial($n-1)

Cái này $n * factorial($n-1); chính là đệ quy. Cách hoạt động của nó được giải thích như sau:

  • factorial(6) = 6 * factorial(5)
  • factorial(5) = 5 * factorial(4)
  • factorial(4) = 4 * factorial(3)
  • factorial(3) = 3 * factorial(2)
  • factorial(2) = 2 * factorial(1)
  • factorial(1) = 1 * factorial(0)
  • factorial(0) = 1

Như vậy chúng ta thấy rằng factorial(6) được tính thông qua factorial(5) và cứ thế cho đến mốc khởi đầu của nó là factorial(0) mà ta biết giá trị chính xác và đệ quy dừng lại ở đây, kết quả là factorial(6) = 6*5*4*3*2*1 = 720. Giả sử bạn thay:

    if($n == 0){
        return 2;
    } 

Kết quả sẽ khác, bạn hãy tự thử xem thế nào!

Giai thừa có lẽ là ví dụ dễ hiểu nhất về đệ quy, giờ chúng ta quay lại cách giải quyết của quick sort.

Trước hết ta xem lại ý tưởng tổng quan của nó:

  • Nó lấy một giá trị để so sánh, ở đây là $pivot
  • Nó tạo ra 2 mảng phụ là $left$right
  • Các phần tử trong mảng cần sắp xếp ban đầu ($arr) được so sánh lần lượt với $pivot, và nếu nhỏ hơn, phần tử này được đưa vào mảng $left, và nếu lớn hơn thì đưa vào mảng $right
  • Tiếp đến nó sử dụng đệ quy với cả $left và $right:
$left = kc_quickSort($left);
$right = kc_quickSort($right);

Đệ quy sẽ dừng lại khi chỉ còn một phần tử. Cuối cùng nó gộp các mảng lại với nhau bằng lệnh:

array_merge($left, array($pivot), $right);

Giờ hãy xem quá trình của nó với dãy 4, 2, 9, 7, 3, 1, 6, 8, 10, 5

Ở đây

  • $pivot = 4
  • $left = 2, 3, 1
  • $right = 9, 7, 6, 8, 10, 5

Tiếp đến $left lại được đệ quy:

  • $pivot_left = 2
  • $left_left = 1
  • $right_left = 3
  • $arr_left = 1, 2, 3

Ở đây $left_left, $right_left ngừng đệ quy vì nó đã chạm đến điều kiện chỉ còn một phần tử trong quá trình chia tách.

Phần đệ quy của $right:

  • $pivot_right = 9
  • $left_right = 7, 6, 8, 5
  • $right_right = 10
  • $arr_right = 7, 6, 8, 5, 9, 10

$arr tổng hợp sau lần đệ quy đầu tiên (của $left và $right): 1, 2, 3, 4, 7, 6, 8, 5, 9, 10

Bạn đã thấy nó có sự sắp xếp dần rồi đúng không? Ngạc nhiên thật! Sự xáo trộn chỉ còn ở phần 7, 6, 8, 5. Sự đệ quy tiếp của $left_right sẽ giải quyết nốt phần này.

Quick sort thực hiện quá trình chia để trị, một mảng lớn được chia làm đôi (thành các mảng nhỏ hơn) để sắp xếp, sau đó các mảng nhỏ hơn cũng được làm như vậy (đệ quy), trong quá trình đó việc sắp xếp được xử lý dần dần, và đến cuối cùng thứ tự được thiết lập.

Back to Top