Thuật Toán Sắp Xếp Nổi Bọt Bubble Sort

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 dù không phải là phương pháp tối ưu cho dữ liệu lớn nhưng nó rất hữu ích mục đích hiểu về cách hoạt động của các thuật toán sắp xếp.

Nguyên Lý Hoạt Động

Thuật toán sắp xếp nổi bọt hoạt động bằng cách duyệt qua danh sách nhiều lần so sánh từng cặp phần tử liền kề với hoán đổi chúng nếu phần tử trước lớn hơn phần tử sau. Quá trình này lặp lại cho đến khi danh sách được sắp xếp hoàn toàn.

Các bước thực hiện

Duyệt qua danh sách từ đầu đến cuối.
So sánh từng cặp phần tử liền kề.
Nếu phần tử trước lớn hơn phần tử sau hoán đổi chúng.
Lặp lại quá trình này cho đến khi không còn hoán đổi nào diễn ra.

Mỗi vòng lặp sẽ đưa phần tử lớn nhất hay nhỏ nhất về đúng vị trí của nó giống như những bong bóng lớn nổi lên mặt nước do đó có tên gọi sắp xếp nổi bọt.

Code Mẫu

Dưới đây là cách triển khai thuật toán sắp xếp nổi bọt bằng Python

def bubble_sort(arr)

n = len(arr)

for i in range(n – 1)

swapped = False

for j in range(n – 1 – i)

if arr[j] > arr[j + 1]: # So sánh hai phần tử liền kề

arr[j], arr[j + 1] = arr[j + 1], arr[j] # Hoán đổi

swapped = True

if not swapped: # Nếu không có hoán đổi nào thì danh sách đã được sắp xếp

break

return arr

# Ví dụ sử dụng

arr = [64, 34, 25, 12, 22, 11, 90]

print(“Mảng sau khi sắp xếp “, bubble_sort(arr))

Giải thích

Biến swapped giúp tối ưu thuật toán bằng cách kiểm tra nếu không có hoán đổi nào diễn ra trong một vòng lặp nghĩa là danh sách đã được sắp xếp có thể dừng thuật toán sớm.
Ở mỗi lần lặp phần tử lớn nhất nổi lên cuối danh sách nên phạm vi duyệt (n-1-i) giảm dần theo mỗi vòng lặp.

Độ Phức Tạp

Trường hợp	Độ phức tạp
Tệ nhất (Worst-case)	O(n²)
Trung bình (Average-case)	O(n²)
Tốt nhất (Best-case khi danh sách đã sắp xếp)	O(n)

Trường hợp tệ nhất và trung bình khi danh sách ngẫu nhiên hoặc ngược thứ tự thuật toán phải thực hiện khoảng n²/2 lần so sánh.
Trường hợp tốt nhất là khi danh sách đã được sắp xếp chỉ cần n lần kiểm tra mà không có hoán đổi nào thì thuật toán dừng sớm.

Khi Nào Nên Dùng Sắp Xếp Nổi Bọt

Mặc dù có độ phức tạp cao nhưng sắp xếp nổi bọt vẫn hữu ích trong một số trường hợp

Dữ liệu nhỏ khi mà danh sách có ít phần tử thì thuật toán này dễ triển khai cả đủ nhanh.
Dữ liệu gần như đã được sắp xếp với tối ưu kiểm tra hoán đổi nên nó có thể hoàn thành trong O(n) thay vì O(n²).
Giáo dục thì là một thuật toán đơn giản dễ hiểu giúp người mới học lập trình nắm bắt được khái niệm sắp xếp.

Sắp xếp nổi bọt là một thuật toán cơ bản khá dễ hiểu nhưng không hiệu quả cho dữ liệu lớn dù vậy nó vẫn có những ứng dụng trong các trường hợp đặc biệt. Nếu cần sắp xếp nhanh hơn thì có thể sử dụng Quick Sort hay Merge Sort hay Heap Sort tùy vào yêu cầu cụ thể.