Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp nổi bọt (tiếng Anh: Bubble Sort) là một thuật toán sắp xếp đơn giản. Nó liên tục duyệt qua trình tự được sắp xếp, so sánh hai phần tử tại một thời điểm và trao đổi chúng nếu chúng sai thứ tự. Công việc duyệt qua trình tự được lặp lại cho đến khi không cần trao đổi nữa, tức là trình tự đã được sắp xếp. Nguồn gốc tên gọi của thuật toán này là do phần tử càng nhỏ sẽ từ từ "nổi" lên đầu dãy thông qua trao đổi.

Hoạt động của thuật toán sắp xếp bong bóng như sau:

• So sánh các phần tử liền kề. Nếu cái đầu tiên lớn hơn cái thứ hai (thứ tự tăng dần), hãy hoán đổi hai cái đó.

• Thực hiện công việc tương tự cho từng cặp phần tử liền kề, từ cặp đầu tiên ở đầu đến cặp cuối cùng ở cuối. Sau khi thực hiện xong bước này, phần tử cuối cùng sẽ là số lớn nhất.

• Lặp lại các bước trên cho tất cả các phần tử ngoại trừ phần tử cuối cùng.

• Tiếp tục lặp lại các bước trên cho ngày càng ít phần tử mỗi lần cho đến khi không còn cặp số nào để so sánh.

Phân tích sắp xếp bong bóng

Sơ đồ quy trình trao đổi (lần đầu):

bong bóng

Sau đó, chúng ta cần thực hiện n-1 quá trình sủi bọt và thời gian so sánh tương ứng cho mỗi lần được thể hiện trong hình sau:

so sánh

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (n) (Có nghĩa là không có phần tử nào có thể được trao đổi sau khi xem qua một lần và việc sắp xếp kết thúc.)

• Độ phức tạp thời gian tồi tệ nhất: O (n 2 )

• Stability: ổn định

Trình diễn sắp xếp bong bóng

hiệu ứng: