Thuật toán sắp xếp nổi bọt (Bubble Sort) với Python

NỘI DUNG

KHÁI NIỆM

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. Cách thức hoạt động của thuật toán này là so sánh hai phần tử kế tiếp trong danh sách và đổi chỗ chúng nếu chúng không được sắp xếp đúng thứ tự. Thuật toán được gọi là “nổi bọt” vì những phần tử nhỏ sẽ được dịch lên trên như bong bóng nổi lên trên mặt nước.

THUẬT TOÁN

Cách hoạt động của thuật toán sắp xếp nổi bọt:

Bắt đầu từ đầu danh sách, so sánh hai phần tử kế tiếp.
Nếu phần tử đứng trước lớn hơn phần tử đứng sau, đổi chỗ hai phần tử này.
Lặp lại quá trình trên cho đến khi không còn phần tử nào được đổi chỗ nữa.
Thuật toán kết thúc khi tất cả các phần tử đã được sắp xếp.

ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n^2), với n là số lượng phần tử cần sắp xếp. Vì vậy, khi sắp xếp một danh sách lớn, thuật toán này sẽ trở nên rất chậm. Tuy nhiên, do đơn giản và dễ hiểu, thuật toán sắp xếp nổi bọt vẫn được sử dụng trong các trường hợp đơn giản hoặc khi danh sách cần sắp xếp đã gần như được sắp xếp trước đó.

VÍ DỤ

Cho danh sách số nguyên [5, 1, 4, 2, 8], sau khi áp dụng thuật toán sắp xếp nổi bọt, danh sách sẽ được sắp xếp thành [1, 2, 4, 5, 8].

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

Lần lượt so sánh và đổi chỗ các phần tử để sắp xếp danh sách:

[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8]

Danh sách đã được sắp xếp.

THUẬT TOÁN SẮP XẾP NỔI BỌT VỚI PYTHON

Dưới đây là một ví dụ về cách triển khai thuật toán sắp xếp nổi bọt bằng ngôn ngữ Python:

def bubble_sort(arr):
    n = len(arr)
    # Lặp qua từng phần tử của danh sách
    for i in range(n):
        # Lặp qua các phần tử còn lại của danh sách
        for j in range(0, n-i-1):
            # So sánh hai phần tử liền kề và đổi chỗ nếu cần thiết
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Sử dụng thử hàm bubble_sort
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Danh sách đã được sắp xếp:")
for i in range(len(arr)):
    print("%d" %arr[i]),

Ở đây, hàm bubble_sort được định nghĩa để sắp xếp danh sách đầu vào bằng thuật toán sắp xếp nổi bọt. Hàm sử dụng hai vòng lặp lồng nhau để lặp qua danh sách và so sánh các phần tử của nó. Khi tìm thấy hai phần tử liền kề không được sắp xếp đúng thứ tự, chúng được đổi chỗ với nhau. Cuối cùng, danh sách đã được sắp xếp được in ra bằng vòng lặp for.

Lập trình Python