Bubble Sort (Sắp Xếp Nổi Bọt)

Bubble Sort là giải thuật sắp xếp đơn giản nhất, hoạt động giống như những bọt khí nhẹ nhàng nổi lên mặt nước.

Cơ Chế Hoạt Động

Ý tưởng chính: Liên tục hoán đổi hai phần tử liền kề nếu chúng đứng sai thứ tự. Sau mỗi lần duyệt qua danh sách (pass), phần tử lớn nhất sẽ "nổi" bong bóng về đúng vị trí cuối cùng của nó.

🎬 Bubble Sort Visualizer

64

34

25

12

22

11

90

45

67

30

Chưa sắp xếp Đang so sánh Đã sắp xếp

Giải Thích Chi Tiết

Giả sử ta muốn sắp xếp mảng tăng dần: [5, 1, 4, 2, 8]

1. Pass 1:

   • So sánh 5 và 1: 5 > 1 -> Hoán đổi -> [1, 5, 4, 2, 8]
   • So sánh 5 và 4: 5 > 4 -> Hoán đổi -> [1, 4, 5, 2, 8]
   • So sánh 5 và 2: 5 > 2 -> Hoán đổi -> [1, 4, 2, 5, 8]
   • So sánh 5 và 8: 5 < 8 -> Giữ nguyên.
   • Kết quả: Số 8 (lớn nhất) đã nằm đúng ở cuối.

2. Pass 2: Lặp lại quy trình, nhưng không cần xét phần tử cuối cùng (8) nữa.

   • Số 5 sẽ nổi về vị trí áp chót.

Quá trình lặp lại cho đến khi không còn cặp nào cần hoán đổi.

Code Implementation

Dưới đây là cài đặt tối ưu với cờ swapped. Nếu trong một lần duyệt không có hoán đổi nào xảy ra, nghĩa là mảng đã sắp xếp xong -> Dừng ngay lập tức (Early Exit).

C++

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // Phần tử cuối cùng i đã vào đúng chỗ
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // Nếu không có swap nào ở vòng lặp trong, dừng luôn
        if (!swapped)
            break;
    }
}

Java

class BubbleSort {
    void bubbleSort(int arr[]) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Java không có swap sẵn kiểu C++
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Tối ưu: Nếu không swap, mảng đã sort xong
        if not swapped:
            break

💡 HPN's Tip

Nhờ cờ biến swapped, Bubble Sort có thể đạt độ phức tạp O(N) trong trường hợp tốt nhất (Best Case) - khi mảng đã được sắp xếp sẵn. Đừng quên tối ưu này khi phỏng vấn nhé!