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

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, 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 và 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.

3. Độ 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: 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, thuật toán dừng sớm.

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

Mặc dù có độ phức tạp cao, 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 danh sách có ít phần tử, thuật toán này dễ triển khai và đủ nhanh.
• Dữ liệu gần như đã được sắp xếp: Với tối ưu kiểm tra hoán đổi, nó có thể hoàn thành trong O(n) thay vì O(n²).
• Giáo dục: 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 hoặc Heap Sort, tùy vào yêu cầu cụ thể.