Bubble Sort trong Python là gì? Giải thích bằng một ví dụ?

Sắp xếp bong bóng là một thuật toán sắp xếp để sắp xếp một danh sách theo thứ tự tăng dần (hoặc giảm dần). Đây là thuật toán sắp xếp đơn giản nhất nhưng không hiệu quả lắm. Nó có thể được sử dụng trên các kích thước đầu vào nhỏ nhưng không hiệu quả về thời gian cho các danh sách hoặc mảng có độ dài lớn hơn. Độ phức tạp thời gian của nó là O (n ^ 2). Tuy nhiên, đây là một thuật toán sắp xếp tại chỗ, có nghĩa là nó không sử dụng thêm bất kỳ khoảng trống nào. Do đó, nó hiệu quả về mặt không gian phức tạp. Tuy nhiên, nó không được sử dụng nhiều vì có các thuật toán sắp xếp tốt hơn so với sắp xếp theo bong bóng.

Bubble Sort hoạt động như thế nào?

Trong sắp xếp bong bóng, hai vòng lặp for được sử dụng. Vòng lặp for bên ngoài lặp lại danh sách. Vòng lặp for bên trong cũng lặp lại danh sách cho tất cả các lần lặp vòng lặp bên ngoài.

Thao tác chính trong Bubble sort là so sánh hai phần tử liên tiếp. Nếu phần tử đầu tiên lớn hơn phần tử tiếp theo, thì hoán đổi cả hai để phần tử nhỏ hơn đi trước và phần tử lớn hơn lùi lại. Trong một lần lặp lại vòng lặp ngoài, phần tử lớn nhất của danh sách nằm ở chỉ mục cuối cùng. Trong lần lặp thứ hai của vòng lặp ngoài, phần tử lớn thứ hai của danh sách nằm ở chỉ mục cuối cùng thứ hai, v.v. Do đó, chúng tôi nhận được danh sách đã sắp xếp ở cuối tất cả các lần lặp.

Chúng tôi có thể hiểu rõ hơn với sự trợ giúp của một ví dụ.

Ví dụ

Chúng tôi bắt buộc phải sắp xếp danh sách sau đây.

Vòng ngoài =1

5> 2, do đó hoán đổi cả hai

5> 1, do đó hoán đổi cả hai

5> 3, do đó hoán đổi cả hai

5> 4, do đó hoán đổi cả hai

(Phần tử lớn nhất 5 đã đạt đến ở chỉ mục cuối cùng sau lần lặp bên ngoài đầu tiên)

Vòng lặp ngoài =2

2> 1, do đó hoán đổi

Không cần hoán đổi

Không cần hoán đổi

Như chúng ta có thể thấy danh sách được sắp xếp trong chính lần lặp thứ 2 bên ngoài. Nhưng vòng lặp bên ngoài sẽ lặp lại 3 lần nữa mà không cần thực hiện thêm thao tác hoán đổi nào. Do đó, chỉ có 2 lần lặp được hiển thị trong ví dụ. Đôi khi, danh sách có thể được sắp xếp trong chính lần lặp đầu tiên. Đôi khi, danh sách có thể được sắp xếp trong lần lặp cuối cùng. Do đó, vòng lặp bên ngoài sẽ luôn lặp lại n lần.

Ví dụ

def bubble_sort(arr):
   for i in range(len(arr)):
      for j in range(len(arr)-1):
         if(arr[j]>arr[j+1]):
            temp=arr[j]
            arr[j]=arr[j+1]
            arr[j+1]=temp
   return arr
array=[2,3,1,5,4]
print(bubble_sort(array))

Đầu ra

[1, 2, 3, 4, 5]