1. Giới thiệu về Thuật toán Sắp xếp Nổi bọt (Bubble Sort)

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp đơn giản nhất. Nó hoạt động bằng cách lặp đi lặp lại qua danh sách cần sắp xếp, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng không theo thứ tự mong muốn. Quá trình này được lặp đi lặp lại cho đến khi toàn bộ danh sách được sắp xếp.

Cách hoạt động:

So sánh từng cặp phần tử: Bắt đầu từ đầu danh sách, so sánh hai phần tử liền kề.

Hoán đổi: Nếu phần tử bên trái lớn hơn phần tử bên phải (trong trường hợp sắp xếp tăng dần), chúng ta sẽ hoán đổi chúng.

Lặp lại: Quá trình so sánh và hoán đổi này được lặp lại cho đến khi không còn sự hoán đổi nào nữa, tức là danh sách đã được sắp xếp hoàn toàn.

2. Cài đặt Thuật toán Sắp xếp Nổi bọt trong PHP

Dưới đây là mã nguồn PHP minh họa cách cài đặt thuật toán sắp xếp nổi bọt:

<?php
function bubbleSort(&$arr) {
    $n = count($arr);
    // Lặp qua toàn bộ mảng
    for ($i = 0; $i < $n; $i++) {
        // Thiết lập cờ kiểm tra để tối ưu hóa
        $swapped = false;
        // Lặp qua các phần tử còn lại trong mảng
        for ($j = 0; $j < $n - $i - 1; $j++) {
            // Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, hoán đổi chúng
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                // Đánh dấu đã có sự hoán đổi
                $swapped = true;
            }
        }
        // Nếu không có sự hoán đổi nào, danh sách đã được sắp xếp và có thể kết thúc
        if (!$swapped) {
            break;
        }
    }
}

// Ví dụ sử dụng
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "Mảng ban đầu:\n";
print_r($arr);

bubbleSort($arr);
echo "Mảng sau khi sắp xếp:\n";
print_r($arr);
?>

Giải thích mã nguồn:

Hàm bubbleSort(&$arr): Hàm này nhận vào một mảng tham chiếu (&$arr) và tiến hành sắp xếp mảng đó.

Vòng lặp đầu tiên (for $i = 0; $i < $n; $i++): Vòng lặp ngoài chạy qua toàn bộ mảng. Sau mỗi lần lặp, phần tử lớn nhất trong số các phần tử chưa được sắp xếp sẽ được đưa đến vị trí đúng của nó.

Vòng lặp thứ hai (for $j = 0; $j < $n - $i - 1; $j++): Vòng lặp này so sánh các phần tử liền kề và hoán đổi chúng nếu không đúng thứ tự.

Cờ kiểm tra swapped: Được sử dụng để kiểm tra xem có sự hoán đổi nào trong vòng lặp hay không. Nếu không có, mảng đã được sắp xếp và thuật toán có thể dừng sớm, tiết kiệm tài nguyên.

3. Phân tích Độ phức tạp của Thuật toán

Độ phức tạp thời gian (Time Complexity):

Trường hợp tốt nhất (Best Case): O(n) – xảy ra khi mảng đã được sắp xếp và không cần hoán đổi nào.
Trường hợp trung bình (Average Case) và trường hợp xấu nhất (Worst Case): O(n^2) – xảy ra khi mảng hoàn toàn không được sắp xếp.

Độ phức tạp không gian (Space Complexity): O(1) – chỉ cần một lượng không gian nhỏ để lưu trữ các biến phụ trợ.

4. Khi nào sử dụng Thuật toán Sắp xếp Nổi bọt

Thuật toán sắp xếp nổi bọt không phải là thuật toán sắp xếp hiệu quả nhất, nhưng nó có thể hữu ích trong một số trường hợp như:

Giáo dục: Bubble Sort thường được sử dụng để dạy các khái niệm cơ bản về sắp xếp và độ phức tạp thuật toán.

Dữ liệu nhỏ: Nếu bạn cần sắp xếp một mảng nhỏ, thuật toán này có thể hoạt động đủ nhanh mà không cần sử dụng các thuật toán phức tạp hơn.

Kiểm tra sự sắp xếp của dữ liệu: Nếu bạn cần kiểm tra xem một mảng có được sắp xếp hay không, bạn có thể sử dụng một phiên bản tối giản của Bubble Sort.

5. Kết luận

Thuật toán sắp xếp nổi bọt tuy đơn giản nhưng lại không hiệu quả đối với các tập dữ liệu lớn do độ phức tạp thời gian cao. Tuy nhiên, nó vẫn là một công cụ hữu ích trong giáo dục và các trường hợp yêu cầu sắp xếp nhanh chóng với dữ liệu nhỏ. Việc hiểu và triển khai thuật toán này trong PHP sẽ giúp bạn nắm vững những kiến thức cơ bản về sắp xếp và thuật toán trong lập trình.

Mạnh Tân Võ