Sắp xếp bong bóng DSA

Sắp xếp bong bóng

Bubble Sort là một thuật toán sắp xếp một mảng từ giá trị thấp nhất đến giá trị cao nhất.

Chạy mô phỏng để xem nó trông như thế nào khi thuật toán Bubble Sort sắp xếp một mảng các giá trị. Mỗi giá trị trong mảng được biểu thị bằng một cột.

Từ “Bong bóng” xuất phát từ cách thức hoạt động của thuật toán này, nó làm cho những giá trị cao nhất “bong bóng lên”.

Tiếp tục đọc để hiểu đầy đủ về thuật toán Bubble Sort và cách tự triển khai nó.

Chạy qua thủ công

Trước khi triển khai thuật toán Bubble Sort trong ngôn ngữ lập trình, chúng ta hãy chạy thủ công qua một mảng ngắn chỉ một lần để có ý tưởng.

Bước 1: Chúng ta bắt đầu với một mảng chưa được sắp xếp.

Bước 2: Chúng ta xét hai giá trị đầu tiên. Giá trị thấp nhất có đến trước không? Có, vì vậy chúng ta không cần phải trao đổi chúng.

Bước 3: Tiến lên một bước và xem xét các giá trị 12 và 9. Giá trị thấp nhất có đến trước không? KHÔNG.

Bước 4: Vì vậy chúng ta cần hoán đổi chúng để 9 đứng đầu.

Bước 5: Tiến lên một bước, nhìn vào số 12 và 11.

Bước 6: Chúng ta phải hoán đổi sao cho 11 đứng trước 12.

Bước 7: Nhìn vào 12 và 3, chúng ta có cần hoán đổi chúng không? Đúng.

Bước 8: Hoán đổi 12 và 3 sao cho 3 đứng trước.

Chạy mô phỏng bên dưới để xem hoạt hình 8 bước trên:

Chạy qua thủ công: Chuyện gì đã xảy ra?

Chúng ta phải hiểu điều gì đã xảy ra trong lần chạy đầu tiên này để hiểu đầy đủ về thuật toán, nhờ đó chúng ta có thể triển khai thuật toán bằng ngôn ngữ lập trình.

Bạn có thể thấy điều gì đã xảy ra với giá trị cao nhất là 12 không? Nó nổi lên đến cuối mảng, nơi nó thuộc về. Nhưng phần còn lại của mảng vẫn chưa được sắp xếp.

Vì vậy, thuật toán Bubble Sort phải chạy qua mảng nhiều lần, nhiều lần, mỗi lần giá trị cao nhất tiếp theo xuất hiện ở đúng vị trí của nó. Việc sắp xếp tiếp tục cho đến khi giá trị thấp nhất còn lại là 3 ở đầu mảng. Điều này có nghĩa là chúng ta cần chạy qua mảng 4 lần để sắp xếp mảng gồm 5 giá trị.

Và mỗi khi thuật toán chạy qua mảng, phần chưa được sắp xếp còn lại của mảng sẽ trở nên ngắn hơn.

Đây là cách thực hiện thủ công đầy đủ trông như thế nào:

Bây giờ chúng ta sẽ sử dụng những gì đã học để triển khai thuật toán Bubble Sort bằng ngôn ngữ lập trình.

Thực hiện sắp xếp bong bóng

Để triển khai thuật toán Bubble Sort trong ngôn ngữ lập trình, chúng ta cần:

1. Một mảng có các giá trị cần sắp xếp.
2. Một vòng lặp bên trong đi qua mảng và hoán đổi các giá trị nếu giá trị đầu tiên cao hơn giá trị tiếp theo. Vòng lặp này phải lặp qua một giá trị ít hơn mỗi lần nó chạy.
3. Vòng lặp bên ngoài kiểm soát số lần vòng lặp bên trong phải chạy. Đối với một mảng có n giá trị, vòng lặp bên ngoài này phải chạy n-1 lần.

Mã kết quả trông như thế này:

 my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n-1):
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]

print("Sorted array:", my_array)

Cải thiện sắp xếp bong bóng

Thuật toán Bubble Sort có thể được cải thiện thêm một chút.

Hãy tưởng tượng rằng mảng gần như đã được sắp xếp sẵn, với các số thấp nhất ở đầu, chẳng hạn như thế này:

 my_array = [7, 3, 9, 12, 11]

Trong trường hợp này, mảng sẽ được sắp xếp sau lần chạy đầu tiên, nhưng thuật toán Bubble Sort sẽ tiếp tục chạy mà không hoán đổi các phần tử và điều đó là không cần thiết.

Nếu thuật toán đi qua mảng một lần mà không hoán đổi bất kỳ giá trị nào thì mảng đó phải được sắp xếp xong và chúng ta có thể dừng thuật toán, như sau:

 my_array = [7, 3, 9, 12, 11]

n = len(my_array)
for i in range(n-1):
    swapped = False
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]
            swapped = True
    if not swapped:
        break

print("Sorted array:", my_array)

Độ phức tạp của thời gian sắp xếp bong bóng

Để có giải thích chung về độ phức tạp của thời gian, hãy truy cập trang này .

Để được giải thích kỹ lưỡng và chi tiết hơn về độ phức tạp của thời gian Sắp xếp nổi bọt, hãy truy cập trang này .

Thuật toán Bubble Sort lặp qua mọi giá trị trong mảng, so sánh nó với giá trị bên cạnh nó. Vì vậy, đối với một mảng các giá trị \(n\), phải có \(n\) những so sánh như vậy trong một vòng lặp.

Và sau một vòng lặp, mảng được lặp đi lặp lại \(n\) lần.

Điều này có nghĩa là có tổng cộng \(n \cdot n\) so sánh được thực hiện, vì vậy độ phức tạp về thời gian của Bubble Sort là:

\[ \underline{\underline{O(n^2)}} \]

Biểu đồ mô tả độ phức tạp về thời gian của Bubble Sort trông như sau:

Như bạn có thể thấy, thời gian chạy tăng rất nhanh khi kích thước của mảng tăng lên.

May mắn thay, có những thuật toán sắp xếp nhanh hơn thuật toán này, như Quicksort , mà chúng ta sẽ xem xét sau.

Bạn có thể mô phỏng Bubble Sort bên dưới, trong đó đường màu đỏ và nét đứt là độ phức tạp về thời gian theo lý thuyết \(O(n^2)\). Bạn có thể chọn một số giá trị \(n\) và chạy triển khai Sắp xếp nổi bong bóng thực tế trong đó các thao tác được tính và số lượng được đánh dấu là dấu thập màu xanh lam trong biểu đồ bên dưới. Lý thuyết so sánh với thực hành như thế nào?

[ , , , , ]