Categories Thuật toán

Thuật toán sắp xếp trộn (merge 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 trộn

Thuật toán tiếp theo mà chúng ta sẽ cùng tìm hiểu sau khi đi qua 2 thuật toán sắp xếp nổi bọt (bubble sort)sắp xếp nhanh (quick sort) là sắp xếp trộn (merge sort).

Sắp xếp trộn có nhiều điểm tương đồng với sắp xếp nhanh, khi nó cũng sử dụng đệ quy làm phương thức. Về tốc độ, bên lập trình nói rằng, trong đa số trường hợp nó nhanh hơn sắp xếp nổi bọt, và tương đương sắp xếp nhanh.

Bài toán: một dãy số không theo thứ tự 4, 2, 9, 7, 3, 1, 6, 8, 10, 5. Yêu cầu sắp xếp theo thứ tự từ nhỏ đến lớn.

Mã mẫu trong PHP:

<?php 
function mergeSort($arr) {
    $len = count($arr);
    if ($len <= 1) return $arr;

    $mid = (int)($len/2);

    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge($left, $right) {
    $result = array();
    $i = 0;
    $j = 0;

    while (count($left) > $i && count($right) > $j) {
        if ($left[$i] > $right[$j]) {
            $result[] = $right[$j];
            $j++;
        } else {
            $result[] = $left[$i];
            $i++;
        }
    }

    while (count($left) > $i) {
        $result[] = $left[$i];
        $i++;
    }

    while (count($right) > $j) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}

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

Giải thích qua:

  • $arr: mảng chứa các phần tử cần sắp xếp
  • $len: số lượng phần tử của mảng, ở đây là 10
  • array_slice($arr, 0, $mid): lấy phần tử từ 0 cho đến phần tử có thứ tự $mid trong mảng $arr
  • array_slice($arr, $mid): lấy phần tử có thứ tự từ $mid + 1 cho đến phần tử cuối cùng trong $arr

Ý tưởng chính:

  • Sắp xếp trộn sẽ chia mảng làm 2 phần có số lượng tương đương nhau sau (nếu chẵn nó sẽ chia đều, nếu lẻ, thì một phần sẽ có nhiều hơn phần còn lại một phần tử). Trong ví dụ trên, 2 mảng được chia sẽ là: 4, 2, 9, 7, 3 và 1, 6, 8, 10, 6
  • Tiếp đến từng phần tử trong mảng sẽ được so sánh với nhau theo thứ tự. Như ở trên 4 sẽ được so với 1, còn 2 được so với 6, cứ thể cho đến cuối là 3 được so với 6. Trong mỗi cặp so sánh đó, phần tử nhỏ sẽ được đưa vào mảng trước (ví chúng ta đang cần sắp xếp từ bé đến lớn), mảng kết quả đó là $result.

Đoạn mã nhận trách nhiệm so sánh cặp đôi này là:

    while (count($left) > $i && count($right) > $j) {
        if ($left[$i] > $right[$j]) {
            $result[] = $right[$j];
            $j++;
        } else {
            $result[] = $left[$i];
            $i++;
        }
    }
  • Quá trình trên là đệ quy, nên cuối cùng phần tử nhỏ nhất sẽ ở vị trí đầu và cứ thế tăng dần cho đến vị trí cuối cùng.

Thế còn đoạn mã bên dưới đây có nhiệm vụ gì?

    while (count($left) > $i) {
        $result[] = $left[$i];
        $i++;
    }

    while (count($right) > $j) {
        $result[] = $right[$j];
        $j++;
    }

Nó được dùng để dự phòng nếu mảng có lẻ phần tử, thì phần tử cuối sẽ vẫn được đưa vào mảng, vì phần tử này chưa được đưa vào trong quá trình so sánh cặp đôi.

Trong đệ quy, luôn có điều kiện kết thúc đệ quy. Với thuật toán sắp xếp trộn nó chính là đoạn mã này: if ($len <= 1) return $arr;

Back to Top