Sắp xếp nổi bọt

5.1 Định nghĩa sắp xếp nổi bọt

Sắp xếp nổi bọt (Bubble Sort) — là một thuật toán sắp xếp đơn giản, nó lặp đi lặp lại qua danh sách và so sánh các phần tử liền kề và thay đổi vị trí của chúng nếu chúng không theo thứ tự đúng. Quá trình này tiếp tục cho đến khi danh sách được sắp xếp hoàn toàn.

Nguyên tắc hoạt động:

1. Thuật toán đi qua danh sách và so sánh từng cặp phần tử liền kề.
2. Nếu các phần tử không theo thứ tự đúng (phần tử đầu tiên lớn hơn phần tử thứ hai đối với sắp xếp tăng dần) — chúng sẽ đổi chỗ.
3. Quá trình này lặp lại cho tất cả các cặp phần tử trong danh sách.
4. Sau mỗi lần đi qua toàn bộ danh sách, phần tử lớn nhất "nổi" lên vị trí của nó (như một cái bong bóng trên mặt nước), và do đó nó không tham gia vào các lần đi qua tiếp theo.
5. Quá trình lặp lại cho đến khi danh sách được sắp xếp.

Độ phức tạp thời gian và không gian của sắp xếp nổi bọt

Độ phức tạp thời gian:

• Trường hợp xấu nhất: O(n^2) — xảy ra khi các phần tử ban đầu được sắp xếp ngược lại.
• Trường hợp trung bình: O(n^2) — xảy ra đối với vị trí ngẫu nhiên của các phần tử.
• Trường hợp tốt nhất: O(n) — xảy ra khi các phần tử đã được sắp xếp (thuật toán có thể được tối ưu hóa cho trường hợp này bằng cách thêm kiểm tra, có sự trao đổi phần tử nào xảy ra trong mỗi lần đi qua).

Độ phức tạp không gian:

O(1) — bởi vì thuật toán sử dụng một lượng bộ nhớ bổ sung không đổi (chỉ vài biến để lưu trữ các giá trị tạm thời).

5.2 Triển khai thuật toán

Thuật toán "sắp xếp nổi bọt" là thuật toán sắp xếp danh sách/mảng đơn giản và nguyên thủy nhất. Nó chỉ đơn giản là so sánh từng cặp phần tử và thay đổi vị trí của chúng nếu cần.

Phiên bản 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Trao đổi phần tử

print("Mảng đã sắp xếp:", array)
# Kết quả: Mảng đã sắp xếp: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Vòng lặp bên trong (được tô màu xanh lá) so sánh phần tử với phần tử bên phải của nó. Và nếu cần, đổi chỗ các phần tử.

Phiên bản 2:

Trong thuật toán của chúng ta có thể thêm tối ưu hóa: sau lần đi qua đầu tiên, phần tử lớn nhất sẽ nằm ở ngoài cùng bên phải, do đó không cần xem xét nó ở vòng lặp tiếp theo.

Sau lần lặp thứ hai, bên phải sẽ có 2 phần tử lớn nhất, do đó vòng lặp bên trong có thể chỉ cần thực hiện đến n - 1 - i. Ở đây i — là số lượng vòng lặp đã qua của vòng lặp bên ngoài.

Phiên bản mới sẽ trông như thế này:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Trao đổi phần tử

print("Mảng đã sắp xếp:", array)
# Kết quả: Mảng đã sắp xếp: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Phiên bản 3:

Ngoài ra, mảng có thể đã gần như được sắp xếp. Do đó, có thể thêm tối ưu hóa như sau: nếu vòng lặp bên trong đi qua tất cả các phần tử mà không có bất kỳ sự trao đổi nào, thì việc sắp xếp đã hoàn thành.

Trong phiên bản này, biến swapped được sử dụng để theo dõi việc có xảy ra sự trao đổi phần tử nào trong lần đi qua cuối cùng không. Nếu sau khi đi qua mảng không có sự trao đổi nào xảy ra, điều đó có nghĩa là mảng đã được sắp xếp và việc thực hiện các vòng lặp tiếp theo là vô nghĩa – chúng không cải thiện được việc sắp xếp. Do đó, biến swapped giúp tối ưu hóa đáng kể tốc độ của thuật toán trên các mảng gần như đã được sắp xếp, kết thúc việc thực hiện sớm.

Triển khai sắp xếp nổi bọt trên Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Tối ưu hóa: kiểm tra xem có xảy ra trao đổi không
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Trao đổi phần tử
                swapped = True
        if not swapped:
            break  # Nếu không có trao đổi, mảng đã được sắp xếp
    return array

# Ví dụ sử dụng:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Mảng đã sắp xếp:", sorted_array)
# Kết quả: Mảng đã sắp xếp: [11, 12, 22, 25, 34, 64, 90]