Thuật toán sắp xếp nổi bọt là một trong những thuật toán cơ bản nhất mà bất kỳ người mới học lập trình nào cũng nên nắm vững để hiểu cách dữ liệu được sắp xếp và xử lý. Từ nguyên lý hoạt động, cách triển khai đến phân tích độ phức tạp, tất cả sẽ được trình bày rõ ràng và dễ hiểu. Hãy cùng CodeGym Đà Nẵng khám phá chi tiết về thuật toán sắp xếp nổi bọt ở bài viết dưới đây nhé. Xem thêm:
- 100 bài tập python có lời giải (Có code mẫu)
- 150+ bài tập JavaScript cơ bản kèm lời giải chi tiết
- Cấu trúc dữ liệu và giải thuật (Data Structures & Algorithms)
Nội dung
Thuật toán sắp xếp nổi bọt là gì?
Thuật toán sắp xếp nổi bọt là một phương pháp sắp xếp đơn giản trong lập trình, hoạt động dựa trên việc 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 đúng thứ tự. Các phần tử lớn dần “nổi” lên cuối danh sách sau mỗi lượt duyệt, giống như bong bóng nổi lên mặt nước. Nhờ cơ chế dễ hiểu và dễ triển khai, thuật toán này thường được dùng để giới thiệu cho người mới học về tư duy thuật toán và kỹ năng xử lý dữ liệu cơ bản. 
Thuật toán sắp xếp nổi bọt
Mô tả chi tiết thuật toán sắp xếp nổi bọt
Ý tưởng
Bạn có thể hình dung thuật toán sắp xếp nổi bọt giống như lúc xếp hàng trong giờ thể dục. Thầy giáo muốn các bạn đứng theo thứ tự từ thấp đến cao nên sẽ lần lượt so sánh chiều cao của từng cặp học sinh đứng cạnh nhau. Nếu bạn đứng bên phải lại thấp hơn bạn đứng bên trái thì thầy cho hai bạn đổi chỗ. Cứ lặp lại như vậy nhiều lần cho đến khi cả hàng được sắp xếp đúng thứ tự.
Giải thích chi tiết thuật toán
Xét một mảng gồm n số nguyên a1, a2, a3, …, an được sắp xếp theo thứ tự không giảm từ trái sang phải, mục tiêu của thuật toán sắp xếp nổi bọt là đưa dần các phần tử có giá trị lớn về cuối dãy. Ta bắt đầu từ vị trí đầu tiên, lần lượt xét từng cặp hai phần tử liền kề. Nếu phần tử bên phải có giá trị nhỏ hơn phần tử bên trái thì hoán đổi vị trí hai phần tử. Nếu không cần đổi, ta tiếp tục chuyển sang cặp kế tiếp. Trong quá trình đó, các phần tử nhỏ hơn sẽ dần xuất hiện ở phía trước, còn phần tử lớn hơn sẽ dịch chuyển về phía bên phải của mảng. Sau khi kết thúc lượt duyệt đầu tiên, phần tử lớn nhất sẽ được đưa về vị trí cuối cùng của dãy. Ở lượt duyệt thứ hai, ta tiếp tục bắt đầu từ đầu mảng, thực hiện lại thao tác so sánh và hoán đổi nhưng chỉ cần xét đến vị trí trước phần tử đã được sắp xếp ở lượt trước. Cứ như vậy, sau mỗi vòng lặp, ta sẽ đưa được phần tử lớn kế tiếp về đúng vị trí của nó ở cuối dãy. Hình minh họa thuật toán sẽ giúp bạn dễ hình dung hơn quá trình các phần tử di chuyển trong mảng. 
Mô tả thuật toán sắp xếp nổi bọt
Xem thêm:
- Java là gì? Tổng quan về ngôn ngữ lập trình Java
- Machine learning là gì? Quy trình triển khai thuật toán ML
- OOP là gì? Giải thích về lập trình hướng đối tượng cho người mới
Giải thuật cho mẫu sắp xếp nổi bọt
Thuật toán C++ tham khảo
// hàm sắp xếp nổi bọt (bubble sort)
void BubbleSort(int a[], int n){
int temp; // biến tạm temp
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}Thuật toán Java tham khảo:
private static void bubbleSort(int[] unsortedArray, int length) {
int temp, counter, index;
for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not.
temp = unsortedArray[index]; //These three lines just swap the two elements:
unsortedArray[index] = unsortedArray[index+1];
unsortedArray[index+1] = temp;
}
}
}
}Thuật toán PHP tham khảo:
$arr = [...];
$arr_count = count($arr);
//loop
for ($i = 0; $i < $arr_count; $i++)
{
for ($j = 1; $j < $arr_count - $i; $j++)
{
if ($arr[$j-1] > $arr[$j])
{
$tmp = $arr[$j-1];
$arr[$j-1] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
for($i=0;$i<$arr_count;$i++){
echo $arr[$i]."
";
}Những lưu ý của thuật toán sắp xếp nổi bọt
Ưu điểm
Thuật toán này thuộc nhóm những phương pháp sắp xếp đơn giản nhất, giúp người mới học dễ dàng nắm bắt cách dữ liệu được so sánh và xử lý. Cách triển khai ngắn gọn, cú pháp rõ ràng nên rất dễ ghi nhớ và áp dụng trong các bài tập cơ bản.
Nhược điểm
Thuật toán sắp xếp nổi bọt có hiệu suất xử lý chậm, được xem là một trong những thuật toán sắp xếp kém tối ưu nhất. Khi áp dụng cho các tập dữ liệu lớn, thời gian thực thi tăng rất nhiều nên hầu như không phù hợp trong các bài toán yêu cầu hiệu năng cao.
Thời gian tính và độ phức tạp
Với mỗi lượt lặp i từ 1 đến n trừ 1, thuật toán phải thực hiện tối đa n trừ i phép so sánh. Như vậy, tổng số phép so sánh và hoán đổi trong trường hợp xấu nhất sẽ bằng tổng của các giá trị từ 1 đến n trừ 1, tức là bằng n nhân n trừ 1 rồi chia cho 2. Do đó, độ phức tạp thời gian của thuật toán sắp xếp nổi bọt trong trường hợp xấu nhất thuộc bậc n bình phương, ký hiệu là O(n²).
Thuật toán sắp xếp nổi bọt tuy đơn giản nhưng lại đóng vai trò quan trọng trong việc giúp người học hiểu rõ cơ chế so sánh và hoán đổi trong các thuật toán sắp xếp. Khi nắm vững nền tảng này, bạn sẽ dễ dàng tiếp cận những thuật toán phức tạp hơn và nâng cao tư duy lập trình. Nếu bạn muốn học lập trình bài bản, rèn luyện tư duy thuật toán và phát triển sự nghiệp IT, hãy đồng hành cùng CodeGym Đà Nẵng để được đào tạo từ căn bản đến nâng cao.
0 Lời bình