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:
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:
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 đó.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ó.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ự.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.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ư:
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.
