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

Trong một buổi phỏng vấn, ứng viên được hỏi: "Hãy giải thích tại sao Bubble Sort là O(n²)." Câu trả lời "vì có hai vòng lặp lồng nhau" khiến người phỏng vấn lắc đầu — hai vòng lặp lồng nhau không tự động nghĩa là O(n²). Điều thực sự cần hiểu là tổng số phép so sánh giảm dần qua mỗi pass, tạo thành chuỗi n-1 + n-2 + ... + 1 = n(n-1)/2.

Bubble Sort chậm — điều đó không ai phủ nhận. Nhưng nó dạy bạn ba bài học nền tảng mà mọi kỹ sư cần nắm vững: tính ổn định (stable sort), sắp xếp tại chỗ (in-place), và tư duy tối ưu hóa — biến worst-case O(n²) thành best-case O(n) chỉ với một biến boolean. Nắm chắc Bubble Sort, bạn có nền tảng để phân tích mọi thuật toán sắp xếp phức tạp hơn.

Bức tranh tư duy

Hình dung một nồi canh đang sôi. Những bọt khí lớn nhất nổi lên mặt nước trước, bọt nhỏ hơn dần dần theo sau. Bubble Sort hoạt động y hệt: sau mỗi lượt duyệt (pass), phần tử lớn nhất chưa đúng vị trí sẽ "nổi" lên cuối mảng.

Quan sát một pass trên mảng [5, 1, 4, 2, 8]:

Pass 1 — phần tử lớn nhất "nổi" về cuối:

  [5, 1, 4, 2, 8]
   ↕  ↕                5 > 1 → swap
  [1, 5, 4, 2, 8]
      ↕  ↕             5 > 4 → swap
  [1, 4, 5, 2, 8]
         ↕  ↕          5 > 2 → swap
  [1, 4, 2, 5, 8]
            ↕  ↕       5 < 8 → giữ nguyên
  [1, 4, 2, 5, 8]
                  ✓ 8 đã "nổi" đúng vị trí cuối

Pass 2 — bỏ qua vị trí cuối (8 đã cố định):

  [1, 4, 2, 5 | 8]
   ↕  ↕                1 < 4 → giữ nguyên
      ↕  ↕             4 > 2 → swap
  [1, 2, 4, 5 | 8]
         ↕  ↕          4 < 5 → giữ nguyên
                  ✓ 5 đã "nổi" đúng vị trí

Pass 3 — không có swap → mảng đã sắp xếp xong, DỪNG.

Điểm mấu chốt: sau pass thứ i, i phần tử lớn nhất đã nằm đúng vị trí ở cuối mảng. Vòng lặp trong chỉ cần duyệt phần chưa sắp xếp — đây chính là cách giảm thiểu phép so sánh thừa.

🎬 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

Cốt lõi kỹ thuật

Cơ chế hoạt động

Bubble Sort lặp qua mảng nhiều lần. Mỗi lần, nó so sánh từng cặp phần tử liền kề và hoán đổi nếu chúng sai thứ tự. Quá trình dừng khi không còn hoán đổi nào xảy ra trong một pass hoàn chỉnh.

Pseudocode:

procedure BubbleSort(A: mảng có n phần tử)
    for i ← 0 to n - 2 do
        swapped ← false
        for j ← 0 to n - i - 2 do
            if A[j] > A[j + 1] then
                swap(A[j], A[j + 1])
                swapped ← true
        if not swapped then
            return       ← mảng đã sắp xếp, thoát sớm

Phiên bản tối ưu với cờ swapped

Phiên bản ngây thơ (naive) luôn chạy đủ n-1 pass kể cả khi mảng đã sắp xếp từ pass thứ hai. Cờ swapped giải quyết vấn đề này: nếu một pass hoàn chỉnh không có bất kỳ hoán đổi nào, mảng đã được sắp xếp — dừng ngay lập tức.

Tối ưu này biến best-case từ O(n²) thành O(n) — một cải thiện đáng kể cho dữ liệu gần như đã sắp xếp.

Triển khai polyglot

C++

#include <algorithm> // std::swap
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Python

def bubble_sort(arr: list[int]) -> None:
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

Java

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

Go

func bubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		swapped := false
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = true
			}
		}
		if !swapped {
			break
		}
	}
}

Tính ổn định (Stability)

Bubble Sort là stable sort — các phần tử có giá trị bằng nhau giữ nguyên thứ tự tương đối ban đầu. Lý do: phép so sánh dùng toán tử > (strictly greater), nên hai phần tử bằng nhau không bao giờ bị hoán đổi. Tính chất này quan trọng khi sắp xếp theo nhiều tiêu chí (multi-key sorting).

Sắp xếp tại chỗ (In-place)

Bubble Sort chỉ cần O(1) bộ nhớ phụ — một biến swapped và một biến tạm cho phép swap. Không cần mảng phụ, không cần đệ quy. Đây là ưu điểm thực sự trên các hệ thống có bộ nhớ hạn chế.

Thực chiến

Tình huống: Phát hiện dữ liệu gần như đã sắp xếp

Bối cảnh: Một hệ thống embedded nhận log từ sensor theo timestamp. Dữ liệu hầu như đã sắp xếp theo thời gian, nhưng đôi khi vài entry bị trễ 1-2 vị trí do network jitter. Mảng nhỏ (dưới 50 phần tử mỗi batch), bộ nhớ RAM cực kỳ hạn chế.

Mục tiêu: Sắp xếp lại batch và phát hiện xem dữ liệu có bị xáo trộn nghiêm trọng hay không.

from dataclasses import dataclass

@dataclass
class SensorLog:
    timestamp: float
    value: float

def sort_and_detect_disorder(logs: list[SensorLog]) -> tuple[list[SensorLog], int]:
    """Sắp xếp log theo timestamp, trả về số lần swap (mức độ xáo trộn)."""
    n = len(logs)
    total_swaps = 0

    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if logs[j].timestamp > logs[j + 1].timestamp:
                logs[j], logs[j + 1] = logs[j + 1], logs[j]
                swapped = True
                total_swaps += 1
        if not swapped:
            break

    return logs, total_swaps

Phân tích:

• Với dữ liệu gần như đã sắp xếp, Bubble Sort chỉ cần 1-2 pass → O(n) thực tế
• Biến total_swaps đo mức độ xáo trộn (inversion count xấp xỉ) — nếu con số này cao bất thường, hệ thống có thể phát cảnh báo về lỗi sensor hoặc network
• Không cần allocate bộ nhớ phụ — phù hợp với embedded constraints
• Nếu mảng lớn hơn hoặc dữ liệu random, Insertion Sort hoặc Timsort sẽ là lựa chọn tốt hơn

Sai lầm điển hình

❌ Sai lầm 1: Quên cờ tối ưu swapped

Vấn đề: Luôn chạy đủ n-1 pass kể cả khi mảng đã sắp xếp.

# SAI: Không có early termination
def bubble_sort_naive(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Tại sao sai: Với mảng đã sắp xếp (best case), phiên bản naive vẫn thực hiện n(n-1)/2 phép so sánh — lãng phí hoàn toàn. Trong production, nếu dữ liệu thường xuyên đến theo thứ tự (log files, time-series), bạn đang biến O(n) thành O(n²) vô cớ.

# ĐÚNG: Early exit khi không còn swap
def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

❌ Sai lầm 2: Sai biên vòng lặp trong (off-by-one)

Vấn đề: Dùng j < n - 1 thay vì j < n - i - 1, khiến vòng lặp trong luôn duyệt cả phần đã sắp xếp.

// SAI: Vòng lặp trong không thu hẹp biên
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1; j++) {  // ← sai: phải là n - i - 1
        if (arr[j] > arr[j + 1])
            std::swap(arr[j], arr[j + 1]);
    }
}

Tại sao sai: Kết quả vẫn đúng, nhưng bạn thực hiện gấp đôi số phép so sánh cần thiết. Sau pass thứ i, i phần tử cuối đã đúng vị trí — so sánh lại chúng là công việc vô ích. Với n = 10.000, sai biên này tạo ra thêm ~25 triệu phép so sánh thừa.

// ĐÚNG: Thu hẹp biên qua mỗi pass
for (int i = 0; i < n - 1; i++) {
    bool swapped = false;
    for (int j = 0; j < n - i - 1; j++) {  // ← đúng: loại bỏ phần đã sort
        if (arr[j] > arr[j + 1]) {
            std::swap(arr[j], arr[j + 1]);
            swapped = true;
        }
    }
    if (!swapped) break;
}

❌ Sai lầm 3: Kết luận "Bubble Sort luôn là O(n²)"

Vấn đề: Nhiều kỹ sư thuộc lòng "Bubble Sort = O(n²)" mà không phân biệt best/average/worst case.

Tại sao sai: Với phiên bản tối ưu (có cờ swapped), nếu mảng đã sắp xếp, thuật toán chỉ cần đúng 1 pass với n-1 phép so sánh và 0 lần swap → O(n). Đây là điểm phỏng vấn kinh điển: khi được hỏi "best case của Bubble Sort là gì?", câu trả lời đúng phải kèm điều kiện — O(n) chỉ khi có cờ early termination.

Under the Hood

Phân tích độ phức tạp

Trường hợp	Time Complexity	Số phép so sánh	Số lần swap	Ghi chú
Best (mảng đã sắp xếp)	O(n)	n - 1	0	Cần cờ swapped
Average (ngẫu nhiên)	O(n²)	~n²/4	~n²/4	Trung bình n(n-1)/4 inversions
Worst (sắp xếp ngược)	O(n²)	n(n-1)/2	n(n-1)/2	Mỗi cặp đều bị hoán đổi

Space Complexity: O(1) — chỉ cần biến swapped và biến tạm cho swap.

Công thức đếm phép so sánh

Ở pass thứ i (đếm từ 0), vòng lặp trong thực hiện n - i - 1 phép so sánh. Tổng:

Σ (n - i - 1) với i từ 0 đến n-2
= (n-1) + (n-2) + ... + 1
= n(n-1)/2
≈ n²/2

Đây là lý do Bubble Sort là O(n²) — không phải "vì có hai vòng lặp", mà vì tổng công việc thực tế tỷ lệ bậc hai với n.

Cache-friendliness và mảng nhỏ

Bubble Sort truy cập bộ nhớ tuần tự (sequential access pattern): luôn so sánh arr[j] và arr[j+1] — hai ô nhớ liền kề. Trên CPU hiện đại, điều này tận dụng tốt cache line (thường 64 bytes). Với mảng nhỏ (n ≤ 20-30), Bubble Sort có thể nhanh hơn các thuật toán phức tạp hơn nhờ ít overhead và cache hit rate cao.

So sánh với Insertion Sort trên dữ liệu gần sắp xếp

Tiêu chí	Bubble Sort (tối ưu)	Insertion Sort
Best case	O(n)	O(n)
Cơ chế phát hiện "đã sắp xếp"	Cờ swapped — kiểm tra cuối mỗi pass	Tự nhiên — vòng lặp trong không chạy
Số phép swap trên nearly-sorted	Có thể nhiều hơn	Ít hơn (dịch chuyển thay vì swap)
Thực tế	Chậm hơn Insertion Sort	Được ưu tiên trong hầu hết trường hợp

Kết luận: nếu cần thuật toán O(n²) đơn giản cho production, Insertion Sort hầu như luôn là lựa chọn tốt hơn Bubble Sort. Bubble Sort có giá trị chính ở khía cạnh giáo dục và phân tích thuật toán.

Checklist ghi nhớ

✅ Checklist triển khai

Cơ chế cốt lõi

• [ ] Mỗi pass đẩy phần tử lớn nhất (chưa đúng vị trí) về cuối mảng
• [ ] Vòng lặp trong thu hẹp biên: j < n - i - 1 — không duyệt lại phần đã sắp xếp
• [ ] Cờ swapped cho phép dừng sớm khi mảng đã sắp xếp

Tính chất quan trọng

• [ ] Stable sort — phần tử bằng nhau giữ nguyên thứ tự ban đầu
• [ ] In-place — O(1) bộ nhớ phụ, không cần mảng tạm
• [ ] Comparison-based — chỉ cần toán tử so sánh, áp dụng cho mọi kiểu dữ liệu

Độ phức tạp

• [ ] Best case O(n) — yêu cầu cờ swapped, mảng đã sắp xếp
• [ ] Average và Worst case O(n²) — tổng so sánh là n(n-1)/2
• [ ] Tổng số swap worst case bằng tổng số so sánh: n(n-1)/2

Khi nào dùng / không dùng

• [ ] Phù hợp: mảng rất nhỏ, dữ liệu gần như đã sắp xếp, bộ nhớ cực kỳ hạn chế
• [ ] Không phù hợp: dữ liệu lớn hoặc ngẫu nhiên — ưu tiên Insertion Sort hoặc thuật toán O(n log n)

Bài tập luyện tập

Bài 1: Đếm số pass — Foundation

Đề bài: Cho mảng [3, 1, 2, 4, 5]. Nếu dùng Bubble Sort tối ưu (có cờ swapped), thuật toán cần bao nhiêu pass để hoàn thành?

🧠 Quiz

Câu hỏi: Mảng [3, 1, 2, 4, 5] cần bao nhiêu pass khi dùng Bubble Sort tối ưu?

• [ ] A. 1 pass
• [x] B. 2 pass
• [ ] C. 3 pass
• [ ] D. 4 pass Giải thích: Pass 1: so sánh và swap (3,1) → [1, 3, 2, 4, 5], swap (3,2) → [1, 2, 3, 4, 5], không swap (3,4) và (4,5). swapped = true nên tiếp tục. Pass 2: duyệt qua [1, 2, 3] — không có swap nào → swapped = false → dừng. Tổng cộng 2 pass. Đáp án A sai vì pass 1 có swap nên chưa kết thúc. Đáp án C, D sai vì pass 2 đã xác nhận mảng đã sắp xếp.

💡 Gợi ý

• Chạy tay từng pass, theo dõi biến swapped
• Pass nào không có swap → thuật toán dừng

Bài 2: Bubble Sort biến thể — Intermediate

Đề bài: Viết hàm cocktail_shaker_sort (Bubble Sort hai chiều): pass lẻ duyệt từ trái sang phải, pass chẵn duyệt từ phải sang trái. Thuật toán này giải quyết vấn đề "turtle" — phần tử nhỏ nằm ở cuối mảng di chuyển rất chậm trong Bubble Sort thông thường.

🧠 Quiz

Câu hỏi: Cocktail Shaker Sort cải thiện Bubble Sort bằng cách nào?

• [ ] A. Giảm worst-case từ O(n²) xuống O(n log n)
• [ ] B. Giảm space complexity từ O(n) xuống O(1)
• [x] C. Giảm số pass cần thiết cho các phần tử nhỏ nằm ở cuối mảng
• [ ] D. Biến thuật toán thành unstable sort để tăng tốc Giải thích: Cocktail Shaker Sort vẫn là O(n²) worst case (A sai). Bubble Sort đã là O(1) space (B sai). Thuật toán vẫn stable vì chỉ swap khi strictly greater (D sai). Điểm cải thiện thực sự: duyệt hai chiều giúp phần tử nhỏ ở cuối mảng ("turtles") di chuyển nhanh hơn về đầu, giảm tổng số pass trong thực tế (C đúng).

💡 Gợi ý

• Duy trì hai biên start và end, thu hẹp từ cả hai phía
• Pass trái→phải đẩy phần tử lớn về cuối, pass phải→trái đẩy phần tử nhỏ về đầu
• Vẫn cần cờ swapped để early termination

✅ Lời giải

def cocktail_shaker_sort(arr: list[int]) -> None:
    n = len(arr)
    start = 0
    end = n - 1
    swapped = True

    while swapped:
        swapped = False

        # Pass trái → phải: đẩy phần tử lớn về cuối
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        end -= 1

        if not swapped:
            break

        swapped = False

        # Pass phải → trái: đẩy phần tử nhỏ về đầu
        for i in range(end, start, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        start += 1

Phân tích: Time O(n²) worst case, O(n) best case. Space O(1). Stable. Cải thiện thực tế so với Bubble Sort khoảng 10-20% trên dữ liệu có "turtles", nhưng vẫn không cạnh tranh được với Insertion Sort hoặc các thuật toán O(n log n).

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• → Selection Sort — Thuật toán O(n²) tiếp theo: chọn phần tử nhỏ nhất thay vì "nổi bọt"
• → Insertion Sort — Đối thủ trực tiếp của Bubble Sort, nhanh hơn trên dữ liệu gần sắp xếp
• ← Phân tích độ phức tạp — Nền tảng để hiểu tại sao n(n-1)/2 = O(n²)

Từ khóa glossary: Bubble Sort, sắp xếp nổi bọt, stable sort, in-place sort, comparison sort, O(n²)

Tìm kiếm liên quan: sắp xếp bọt, giải thuật sắp xếp cơ bản, thuật toán sắp xếp đơn giản, so sánh bubble sort insertion sort