Categories Thuật toán

Thuật toán sắp xếp nổi bọt (bubble 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 nổi bọt

Bài toán: chúng ta có một tập hợp các phần tử với các giá trị khác nhau, nhưng không theo thứ tự nào cả.

Yêu cầu: sắp xếp lại thứ tự của nó từ nhỏ đến lớn.

Lời ngỏ: hầu hết các ngôn ngữ lập trình đều có sẵn các hàm để giải quyết những bài toán cơ bản kiểu như thế này, vấn đề ở đây là chúng ta cần luyện tư duy, sử dụng các hàm cơ bản hơn để đạt yêu cầu đề ra. Ngôn ngữ lập trình nào ở đây không quá quan trọng, bạn nắm rõ thuật toán thì ngôn ngữ nào bạn cũng sẽ viết được.

Giới thiệu: thuật toán sắp xếp nổi bọt như ngụ ý hình tượng của nó, sẽ duyệt qua danh sách tất cả các phần tử của nhóm và so sánh mỗi cặp phần tử liền kề, nếu thứ tự của nó không như yêu cầu thì đổi chỗ (hoán vị). Quá trình này được lặp lại cho đến khi tất cả các phần tử ở đúng vị trí, và bài toán được giải quyết.

Ví dụ, chúng ta có tập hợp phần tử sau: 1, 20, 9 ,7, 3, 4, 6, 8, 2, 5, 30, 27

Hàm minh họa trong PHP (bạn có thể sử dụng ứng dụng online kiểu như https://onlinephp.io/ để test hàm nếu chưa muốn cài các phần mềm chạy PHP trên máy tính):

<?php
$arr = array(1, 20, 9 , 7, 3, 4, 6, 8, 2, 5, 30, 27);

function kc_bubble_sort($arr) {
    // đếm số lượng phần tử
    $size = count($arr);

    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-1-$i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                // hoán vị phần tử
                $temp = $arr[$j]; // phần tử trung gian
                $arr[$j] = $arr[$j+1]; // đảo lần 1
                $arr[$j+1] = $temp; // đảo lần 2, hoán vị thành công
            }
        }
    }

    return $arr;
}

$arr = kc_bubble_sort($arr);

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

Giải thích:

  • Chúng ta bắt đầu với phần hoán vị, if ($arr[$j] > $arr[$j+1]) nghĩa là nếu phần tử đứng trước lớn hơn phần tử đứng sau chúng ta sẽ phải đảo vị trí của nó (theo yêu cầu là sắp xếp từ nhỏ đến lớn), bằng đoạn mã bên dưới:
// hoán vị phần tử
$temp = $arr[$j]; // phần tử trung gian
$arr[$j] = $arr[$j+1]; // đảo lần 1
$arr[$j+1] = $temp; // đảo lần 2, hoán vị thành công

Câu hỏi ở đây $temp để làm gì, sao không chỉ như thế này thôi là đủ:

$arr[$j] = $arr[$j+1]; 
$arr[$j+1] = $arr[$j]; 

Nguyên nhân là vì, sau khi bạn gán giá trị $arr[$j] = $arr[$j+1]; thì $arr[$j] đã có giá trị mới rồi (chính là giá trị của $arr[$j+1]), nên nếu tiếp tục gán $arr[$j+1] = $arr[$j]; chúng ta sẽ có 2 giá trị trùng lặp đều là của $arr[$j+1], thay vì có giá trị hoán vị. $temp chính là nơi lưu giá trị tạm thời của $arr[$j].

Phần trên đã dễ hiểu, nhưng còn đoạn này thì sao:

for ($j=0; $j<$size-1-$i; $j++) {
     // đoạn mã hoán vị
}

Sao nó không phải là như thế này:

for ($j=0; $j<$size; $j++) {
     // đoạn mã hoán vị
}

Thực tế khi bạn chạy đoạn mã bên dưới đây:

<?php
$arr = array(1, 20, 9 , 7, 3, 4, 6, 8, 2, 5, 30, 27);

function kc_bubble_sort($arr) {
    // đếm số lượng phần tử
    $size = count($arr);

    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                // hoán vị phần tử
                $temp = $arr[$j]; // phần tử trung gian
                $arr[$j] = $arr[$j+1]; // đảo lần 1
                $arr[$j+1] = $temp; // đảo lần 2, hoán vị thành công
            }
        }
    }

    return $arr;
}

$arr = kc_bubble_sort($arr);

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

Nó sẽ báo lỗi:

Notice: Undefined offset: 12 in /home/user/scripts/code.php on line 10

Notice: Undefined offset: 12 in /home/user/scripts/code.php on line 13

Sở dĩ có điều đó là vì với đoạn mã trên, đến phần tử cuối cùng sẽ không tồn tại $arr[$j+1] nữa (trong ví dụ trên nó có 12 phần tử, đoạn mã for ($j=0; $j<$size; $j++) {} khi đến phần tử cuối sẽ thực hiện kiểm tra $arr[11] > $arr[12], mảng được đánh vị trí từ 0, do vậy mảng này chỉ có đến phần tử $arr[11] là tối đa, không có $arr[12]).

OK, như vậy là sẽ hợp lý nếu nó như sau phải không:

<?php
$arr = array(1, 20, 9 , 7, 3, 4, 6, 8, 2, 5, 30, 27);

function kc_bubble_sort($arr) {
    // đếm số lượng phần tử
    $size = count($arr);

    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-1; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                // hoán vị phần tử
                $temp = $arr[$j]; // phần tử trung gian
                $arr[$j] = $arr[$j+1]; // đảo lần 1
                $arr[$j+1] = $temp; // đảo lần 2, hoán vị thành công
            }
        }
    }

    return $arr;
}

$arr = kc_bubble_sort($arr);

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

Với $j<$size-1 là đoạn mã trên sẽ chạy, trả về đúng kết quả mà không báo lỗi gì, còn chốc nữa tôi sẽ giải thích tại sao là $j<$size-1-$i (giải thích luôn bây giờ sẽ rối).

Giờ chúng ta sẽ qua phần hiểu đoạn mã trên đã, xem nó bắt đầu như thế nào?

Ở vòng lặp đầu tiên của $j, tức là $j = 0, nó sẽ so sánh 1, 20. Không có thay đổi gì, vì 1 nhỏ hơn 20. Tiếp:

  • $j = 1. So sánh 20 và 9, và sẽ có hoán vị, thứ tự lúc này là 1, 9, 20
  • $j = 2. So sánh 20 và 7 (không phải 9 và 7 vì lúc này, 20 đã lấy vị trí của 9 rồi), có hoán vị, thứ tự lúc này là 1, 9, 7, 20
  • Cứ như vậy cho đến $j = 11, chúng ta sẽ có kết quả như sau: 1, 9, 7, 3, 4, 6, 8, 2, 5, 20, 27, 30
  • Ý tưởng nổi bọt ở đây đã dễ hiểu hơn, giá trị nhỏ hơn sẽ được nổi lên trước, như bong bóng nước nhẹ hơn nổi lên trên và viên sỏi nặng chìm xuống dưới.
  • Lưu ý là chúng ta có 2 vòng lặp lồng nhau, và vòng lặp $j chạy hết lượt đầu tiên của nó chỉ làm cho viên sỏi nặng nhất chìm xuống dưới cùng, ở đây là giá trị 30.
  • Và để sắp xếp hoàn chỉnh chúng ta cần chạy đủ các vòng lặp $i, để các giá trị lớn hơn dần chìm hết xuống.

Để dễ hiểu bạn có thể chạy đoạn mã sau:

<?php
$arr = array(1, 20, 9 , 7, 3, 4, 6, 8, 2, 5, 30, 27);

function kc_bubble_sort($arr) {
    // đếm số lượng phần tử
    $size = count($arr);

    for ($i=0; $i<1; $i++) {
        for ($j=0; $j<$size-1; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                // hoán vị phần tử
                $temp = $arr[$j]; // phần tử trung gian
                $arr[$j] = $arr[$j+1]; // đảo lần 1
                $arr[$j+1] = $temp; // đảo lần 2, hoán vị thành công
            }
        }
    }

    return $arr;
}

$arr = kc_bubble_sort($arr);

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

Tức là chỉ chạy một vòng cho $j, kết quả sẽ thành như phần mô tả ở trên:

1, 9, 7, 3, 4, 6, 8, 2, 5, 20, 27, 30

Còn nếu bạn chạy 2 vòng $j, tức là để $i<2 thì kết quả sẽ như thế này:

1, 7, 3, 4, 6, 8, 2, 5, 9, 20, 27, 30

OK, như vậy là chúng ta đã hiểu rằng, với mỗi vòng lặp hoàn chỉnh của $j (chạy hết vòng) thì giá trị lớn nhất sẽ chìm xuống dưới và dần dần khi chạy đủ chúng ta sẽ có mảng sắp xếp theo đúng thứ tự mong muốn.

Giờ câu hỏi cuối cùng sẽ là, vì sao ở mã chuẩn là lại trừ cả thêm $i:

for ($j=0; $j<$size-1-$i; $j++) {

Nguyên nhân là vì sau mỗi vòng lặp hoàn chỉnh của $j, giá trị lớn nhất đã nằm ở cuối, và như vậy không cần phải so sánh với phần tử đó nữa. Nói cách khác, chẳng hạn sau 2 vòng lặp hoàn chỉnh của $j, chắc chắn 2 giá trị lớn nhất đã nằm ở cuối rồi, do vậy không cần tiếp tục so sánh với 2 phần tử đó làm gì, do vậy mà trừ đi.

Mục đích của đoạn mã này vì thế là để tiết kiệm tài nguyên. Lập trình thường có những thao tác lặp đi lặp lại rất nhiều lần (không hiếm gặp là cả 100 ngàn phép tính mỗi lần chạy ứng dụng), và đôi khi, chỉ một điều chỉnh nhỏ trong đoạn mã có thể giúp giảm thời gian thực thi hoặc/và tài nguyên yêu cầu đi vài lần. Qua đó cải thiện trải nghiệm người dùng, tiết kiệm chi phí máy chủ.

Đánh giá về thuật toán sắp xếp nổi bọt: thuật toán này được cho là dễ hiểu nhưng so với các thuật toán sắp xếp khác nó có tốc độ chậm hơn (ví dụ khi so với quick sort hoặc merge sort), nó cần tối thiểu n*(n-1)/2 bước so sánh cặp đôi để sắp xếp n phần tử.

OK. Vậy là chúng ta đã hiểu về thuật toán sắp xếp nổi bọt, bằng cách chia nhỏ và giải thích từng phần một của đoạn mã. Đây cũng là biện pháp thường dùng trong lập trình, một bài toán lớn được chia làm nhiều bài toán nhỏ dễ hơn, và giải quyết dần dần. Hẹn gặp lại các bạn ở bài viết sau.

Back to Top