[Mỗi ngày 1 thuật toán] Thuật toán sắp xếp nổi bọt (Bubble Sort)

Chuỗi series nóng hổi “Mỗi ngày 1 thuật toán” vừa ra lò với mong muốn giúp các bạn sinh viên IT vượt qua kiếp nạn “thai lị” CTDL&GT.

1.Ý tưởng của thuật toán sắp xếp nổi bọt

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 và dễ hiểu nhất. Ý tưởng chính của nó là lặp đi lặp lại so sánh từng cặp phần tử liền kề trong một danh sách, và hoán đổi vị trí của chúng nếu chúng không theo thứ tự đúng.
Cụ thể, thuật toán sẽ lặp qua danh sách nhiều lần. Trong mỗi lần lặp:
So sánh từng cặp phần tử liền kề.
Nếu phần tử đứng trước lớn hơn phần tử đứng sau, hoán đổi vị trí của chúng.
Sau mỗi lần lặp, phần tử lớn nhất sẽ “nổi lên” (như bọt) ở cuối danh sách.
Quá trình này được lặp lại cho đến khi toàn bộ danh sách được sắp xếp theo thứ tự tăng dần hoặc giảm dần.

2. Ví dụ

Với danh sách ban đầu [5, 2, 9, 1, 7]:
Lần lặp 1: [2, 5, 1, 7, 9] (hoán đổi 5 và 2)
Lần lặp 2: [2, 1, 5, 7, 9] (hoán đổi 5 và 1)
Lần lặp 3: [1, 2, 5, 7, 9] (hoán đổi 2 và 1)
Lần lặp 4: [1, 2, 5, 7, 9] (không cần hoán đổi)
Như vậy, sau 4 lần lặp, danh sách đã được sắp xếp hoàn toàn.

3. Hình ảnh minh họa

4. Mã nguồn dạng pseudo-code:

5. Mã nguồn trong Java:

6. Mã nguồn trong PHP:

7. Mã nguồn trong Python:

Theo bạn, thuật toán Sắp xếp nổi bọt có những ưu điểm và nhược điểm gì?