Thuật toán sắp xếp (Bubble, Insertion, Quick Sort)

1. Tổng quan

A. Định nghĩa

Thuật toán sắp xếp (Sorting Algorithm) là kỹ thuật sắp xếp lại một tập dữ liệu cho trước theo đúng thứ tự dựa trên tiêu chí do người dùng chỉ định (tăng/giảm dần); đây là thuật toán cơ bản nhất và chi phối hiệu quả của các phép toán khác như tìm kiếm, trộn, tổng hợp.

Sắp xếp là một trong những bài toán được nghiên cứu lâu đời nhất trong khoa học máy tính và trên thực tế nằm ở tầng đáy của hầu hết mọi hệ thống ứng dụng. Việc xây dựng chỉ mục cơ sở dữ liệu, sắp xếp trước cho tìm kiếm nhị phân, loại bỏ trùng lặp, tính trung vị và phân vị trong xử lý thống kê đều lấy sắp xếp làm tiền đề. Vì sao sắp xếp lại quan trọng? Vì trên dữ liệu đã sắp xếp, tìm kiếm nhị phân cho phép tra cứu O(log n) và có thể loại bỏ các phần tử trùng liền kề trong O(n), nên độ phức tạp của các phép toán về sau giảm mạnh. Ngược lại, nếu sắp xếp chậm thì mọi phép toán xếp chồng lên nó cũng chậm theo.

B. Ba trục để hiểu sắp xếp: thời gian, tính ổn định, bộ nhớ

Cốt lõi để hiểu các thuật toán sắp xếp là "sự đánh đổi giữa độ phức tạp thời gian, tính ổn định và bộ nhớ bổ sung". Các thuật toán đơn giản (bubble, insertion, selection) dễ hiểu và dễ cài đặt nhưng chậm dần một cách gay gắt về O(n²) khi dữ liệu lớn lên, trong khi các thuật toán dựa trên chia để trị (quick, merge) nhanh hơn nhiều với trung bình O(n log n) nhưng cài đặt phức tạp hoặc đòi hỏi bộ nhớ bổ sung. Thêm vào đó là "có bảo toàn thứ tự tương đối của các giá trị bằng nhau không (tính ổn định)" và "dùng bao nhiêu bộ nhớ bổ sung (có tại chỗ không)", làm thay đổi lựa chọn phù hợp cho từng tình huống.

Sự đánh đổi này không phải lý thuyết trừu tượng mà chi phối trực tiếp các lựa chọn thực tế. Ví dụ, nếu dữ liệu gần như đã sắp xếp thì insertion sort đơn giản lại nhanh hơn quicksort; với dữ liệu ngẫu nhiên lớn thì quicksort có lợi; và trong môi trường nhúng bị hạn chế bộ nhớ cực độ thì sắp xếp tại chỗ không dùng bộ nhớ bổ sung là bắt buộc. Nói cách khác, không có đáp án tuyệt đối cho "sắp xếp nhanh nhất"; tối ưu thay đổi theo kích thước, trạng thái ban đầu, ràng buộc bộ nhớ và yêu cầu về tính ổn định của dữ liệu.

C. Tính ổn định và sắp xếp tại chỗ

Sắp xếp ổn định (Stable Sort) là việc giữ nguyên thứ tự ban đầu của các phần tử có giá trị bằng nhau, điều mang tính quyết định trong sắp xếp đa tiêu chí (thứ nhất theo tên, thứ hai theo tuổi). Khi sắp xếp trước theo tên rồi sắp xếp lại theo tuổi, phép sắp xếp theo tuổi phải ổn định thì thứ tự theo tên mới được bảo toàn trong cùng một độ tuổi. Sắp xếp tại chỗ (in-place) là việc gần như không dùng bộ nhớ bổ sung (O(1)–O(log n)) ngoài mảng đầu vào, có lợi trong môi trường hạn chế bộ nhớ. Hai tính chất này độc lập với nhau, nên tồn tại cả sắp xếp ổn định nhưng dùng bộ nhớ bổ sung (merge) lẫn sắp xếp tại chỗ nhưng không ổn định (quick).

2. Phân loại thuật toán sắp xếp

Các thuật toán sắp xếp chia rộng thành dựa trên so sánh (comparison-based) và không dựa trên so sánh (non-comparison). Loại dựa trên so sánh xác định thứ tự bằng cách so sánh các phần tử với nhau, và đã được chứng minh rằng cận dưới của số lần so sánh về mặt lý thuyết là O(n log n). Loại không dựa trên so sánh (counting, radix, bucket) khai thác trực tiếp phân bố giá trị hoặc số chữ số để đạt O(n) trong một số điều kiện, nhưng có ràng buộc về khoảng giá trị dữ liệu. Sơ đồ phân loại dưới đây cho thấy vị trí của ba thuật toán mà chủ đề này đề cập.

flowchart TB
  ROOT["Thuật toán sắp xếp"] --> CMP["Dựa trên so sánh (cận dưới O(n log n))"]
  ROOT --> NCMP["Không dựa trên so sánh (counting/radix/bucket)"]
  CMP --> SIMPLE["Đơn giản O(n mũ 2)"]
  CMP --> ADV["Nâng cao O(n log n)"]
  SIMPLE --> BUB["Bubble sort"]
  SIMPLE --> INS["Insertion sort"]
  SIMPLE --> SEL["Selection sort"]
  ADV --> QUICK["Quicksort (chia để trị)"]
  ADV --> MERGE["Merge sort (chia để trị)"]
  ADV --> HEAP["Heap sort"]

Trong phân loại này, bubble sort và insertion sort thuộc họ đơn giản O(n²), còn quicksort thuộc họ chia để trị nâng cao O(n log n). Họ đơn giản có giá trị giáo dục lớn khi cho thấy trực quan "vì sao sắp xếp lại khó", còn họ nâng cao là thứ thực sự được dùng trong thực tế. Đặt ba thuật toán cạnh nhau là cách tốt nhất để hiểu khoảng cách giữa O(n²) và O(n log n) đến từ đâu.

3. Bubble Sort

Phương pháp lặp đi lặp lại việc so sánh hai phần tử liền kề và hoán đổi nếu chúng sai thứ tự, khiến giá trị lớn nổi dần về cuối mảng như bọt nước.

Bubble sort quét mảng một lượt từ đầu đến cuối, so sánh và hoán đổi các phần tử liền kề. Khi một lượt (pass) kết thúc, giá trị lớn nhất được cố định ở cuối cùng. Lượt tiếp theo quét lại, loại trừ phần tử cuối đã cố định, để cố định giá trị lớn thứ hai, và lặp lại điều này n-1 lần thì cả mảng được sắp xếp. Cái tên bắt nguồn từ hình ảnh giá trị lớn nổi về cuối như bọt trên mặt nước.

Đặc điểm lớn nhất của bubble sort là cài đặt đơn giản nhất. Nó được hoàn thành với một vòng lặp kép và một dòng hoán đổi (swap), nên được dùng rộng rãi trong giáo dục nhập môn thuật toán. Tuy nhiên, vì lặp lại so sánh và hoán đổi liền kề ở mỗi lượt, hiệu năng thực tế của nó tệ nhất. Với n phần tử, xảy ra khoảng n²/2 lần so sánh và hoán đổi, nên nó chậm dần gay gắt chỉ với một chút tăng dữ liệu.

Một tối ưu là kỹ thuật cờ (flag) dừng lại nếu không có lần hoán đổi nào trong một lượt, vì mảng đã được sắp xếp. Áp dụng tối ưu này cho phép kết thúc trong O(n) với đầu vào đã sắp xếp sẵn. Nhưng với dữ liệu ngẫu nhiên nó vẫn là O(n²), nên dù có tối ưu này, bubble sort vẫn mang tính giáo dục hơn là thực tiễn.

• Độ phức tạp: thời gian trung bình/tệ nhất O(n²), tốt nhất O(n) (khi tối ưu), không gian O(1), sắp xếp ổn định
• Công dụng: giáo dục / dữ liệu rất nhỏ. Không phù hợp cho sắp xếp quy mô lớn thực tế.

4. Insertion Sort

Phương pháp lần lượt lấy từng phần tử mới và chèn nó vào đúng vị trí trong một mảng con đã sắp xếp, giống hệt cách sắp xếp các lá bài trên tay.

Insertion sort bắt đầu từ phần tử thứ hai, chèn nó vào đúng chỗ bằng cách so sánh với đoạn đã sắp xếp phía trước. Trong khi tìm vị trí chèn, các phần tử lớn hơn nó bị đẩy lùi một ô. Nó giống hệt động tác nhét một lá bài mới nhận vào giữa các lá bài đã sắp xếp trên tay, nên rất dễ hiểu một cách trực quan.

Điểm mạnh quyết định của insertion sort là nhạy cảm với trạng thái ban đầu của đầu vào. Trường hợp tệ nhất (thứ tự đảo ngược) là O(n²), nhưng với dữ liệu gần như đã sắp xếp, hầu như không có phép so sánh nào xảy ra nên nó tiến đến O(n) và rất nhanh. Đó là vì nếu mỗi phần tử đã ở gần đúng chỗ thì hầu như không có phần tử nào cần đẩy lùi. Nhờ tính chất thích nghi (adaptive) này, với dữ liệu quy mô nhỏ hoặc đã sắp xếp một phần, nó có thể còn thực tiễn hơn cả quicksort.

Chính vì tính chất này, insertion sort được dùng trong thực tế như một công cụ phụ trợ cho các sắp xếp khác. Khi quicksort hay merge sort đệ quy chia mảng thành các mảnh nhỏ hơn, khi kích thước mảng con đủ nhỏ (thường 10–32) trở xuống, nó chuyển sang insertion sort thay vì chia để trị vốn có chi phí đệ quy lớn. Ở các mảng nhỏ, hệ số hằng số nhỏ của insertion sort lại khiến nó nhanh hơn.

• Độ phức tạp: thời gian trung bình/tệ nhất O(n²), tốt nhất O(n), không gian O(1), sắp xếp ổn định
• Công dụng: dữ liệu quy mô nhỏ/đã sắp xếp một phần, giai đoạn hoàn thiện của các sắp xếp lai.

5. Quick Sort

Thuật toán chia để trị (Divide and Conquer) chọn một chốt (pivot), phân hoạch mảng thành các giá trị nhỏ hơn và lớn hơn nó, rồi đệ quy sắp xếp lại từng phần.

Quicksort thực hiện phân hoạch (partition) chia mảng thành hai nhóm (giá trị nhỏ hơn chốt, giá trị lớn hơn) dựa trên chốt. Khi phân hoạch xong, chốt cố định vị trí sắp xếp cuối cùng của nó, và đệ quy sắp xếp mảng con trái và phải theo cùng cách thì cả mảng được sắp xếp. Sơ đồ dưới đây cho thấy chia để trị đệ quy chia và ghép lại mảng ra sao.

flowchart TB
  A["Mảng: 5 3 8 1 9 2 (chốt=5)"] --> L["Nhỏ hơn: 3 1 2"]
  A --> P["Chốt cố định: 5"]
  A --> R["Lớn hơn: 8 9"]
  L --> L1["chốt=3 -> 1 2 | 3"]
  R --> R1["chốt=8 -> 8 | 9"]
  L1 --> RES["Kết quả ghép: 1 2 3 5 8 9"]
  R1 --> RES

Quicksort được dùng rộng rãi như sắp xếp nhanh nhất về trung bình. Đó là vì nó gần như sắp xếp tại chỗ (chỉ dùng ngăn xếp đệ quy) và có tính cục bộ bộ nhớ đệm tốt, cho hệ số hằng số nhỏ. Tuy nhiên nó có một điểm yếu chí tử. Nếu chọn chốt kém, phân hoạch lệch về một phía và nó suy biến về tệ nhất O(n²). Ví dụ, luôn chọn phần tử đầu làm chốt trên dữ liệu đã sắp xếp sẵn thì mỗi lần chỉ tách ra một phần tử, cần n lần phân hoạch.

Để tránh trường hợp tệ nhất này, thực tế tinh chỉnh chiến lược chọn chốt. Tiêu biểu là median-of-three, dùng trung vị của các giá trị ở ba điểm (đầu, giữa, cuối) làm chốt, và randomized quicksort, chọn chốt ngẫu nhiên. Ngẫu nhiên hóa ngăn một đầu vào cụ thể luôn gây ra trường hợp tệ nhất, nên có thể kỳ vọng trung bình O(n log n) với mọi đầu vào. Kỹ thuật Introsort cũng được dùng, chuyển sang heap sort khi độ sâu đệ quy tăng quá lớn, bảo đảm tệ nhất O(n log n).

• Độ phức tạp: thời gian trung bình O(n log n), tệ nhất O(n²), không gian O(log n) (ngăn xếp đệ quy), sắp xếp không ổn định
• Công dụng: sắp xếp tốc độ cao đa dụng cho dữ liệu ngẫu nhiên lớn (C++ STL, v.v.).

6. So sánh và ví dụ

Sự khác biệt giữa ba thuật toán rốt cuộc nằm ở "thực hiện so sánh và hoán đổi ít lãng phí đến đâu". Bubble và insertion chỉ xử lý phần tử liền kề, nên một lần so sánh không thể đưa phần tử đi xa, giữ chúng ở O(n²); quicksort chia phần tử thành các nhóm cỡ một nửa trong một nhát qua phân hoạch theo chốt, đạt O(n log n). Bảng và biểu đồ dưới đây tổng hợp sự khác biệt này.

Thuật toán	Trung bình	Tệ nhất	Tốt nhất	Không gian	Ổn định	Đặc điểm cốt lõi
Bubble sort	O(n²)	O(n²)	O(n)	O(1)	Ổn định	Hoán đổi liền kề, giáo dục
Insertion sort	O(n²)	O(n²)	O(n)	O(1)	Ổn định	Mạnh với dữ liệu sắp xếp một phần, thích nghi
Quicksort	O(n log n)	O(n²)	O(n log n)	O(log n)	Không ổn định	Chia để trị, nhanh nhất về trung bình

{
  "type": "bar",
  "data": {
    "labels": ["Bubble", "Insertion", "Quick"],
    "datasets": [{
      "label": "Phép so sánh trung bình (n=1000, tương đối)",
      "data": [1000000, 250000, 10000],
      "backgroundColor": ["#e11d48", "#f59e0b", "#2f6fed"]
    }]
  },
  "options": {
    "plugins": { "legend": { "display": false }, "title": { "display": true, "text": "So sánh khối lượng phép toán trung bình (ví dụ khái niệm)" } },
    "scales": { "y": { "title": { "display": true, "text": "Số phép toán (tương đối)" } } }
  }
}

Biểu đồ trên cho thấy sự khác biệt về khối lượng phép toán giữa họ O(n²) (bubble, insertion) và họ O(n log n) (quick) tại n=1000 kịch tính đến mức nào. Tại n=1000, O(n²) khoảng một triệu và O(n log n) khoảng mười nghìn — chênh lệch một trăm lần — và dữ liệu càng lớn thì khoảng cách này càng giãn theo cấp số nhân. Tại n=1.000.000, O(n²) khoảng 10¹² phép toán và O(n log n) khoảng 2×10⁷; ở mức một tỷ phép toán mỗi giây, đó là khoảng 1.000 giây so với 0,02 giây — chính là ranh giới giữa khả thi và bất khả thi.

Như một ví dụ cụ thể, khi cơ sở dữ liệu xử lý mệnh đề ORDER BY, nó dùng họ quicksort/Introsort nếu có thể nạp vào bộ nhớ, và merge sort ngoài dựa trên đĩa (external merge sort) nếu vượt quá bộ nhớ. Ngược lại, khi duy trì và chèn vào một luồng gần như đã sắp xếp trong thời gian thực (ví dụ dấu thời gian của log), họ insertion sort có lợi vì tiến đến O(n).

7. Đi sâu: Sắp xếp lai trong các thư viện thực tế

Nhận định quan trọng nhất trong thực tế là "không dùng nguyên một thuật toán đơn lẻ". Các thư viện chuẩn áp dụng sắp xếp lai kết hợp điểm mạnh của nhiều thuật toán.

Java (sắp xếp đối tượng trong Arrays.sort) và Python (sorted, list.sort) dùng Timsort. Timsort kết hợp merge sort và insertion sort; nếu trong dữ liệu đã có các đoạn đã sắp xếp (run), nó phát hiện và trộn chúng, nên tiến đến O(n) trên dữ liệu thực tế (thường đã sắp xếp một phần). Việc nó là sắp xếp ổn định cũng quan trọng cho sắp xếp đa tiêu chí.

std::sort của C++ STL dùng Introsort. Nó bắt đầu bằng quicksort theo mặc định nhưng chuyển sang heap sort nếu độ sâu đệ quy vượt 2·log n (một tín hiệu đang hướng đến trường hợp tệ nhất), bảo đảm O(n log n) ngay cả trong trường hợp tệ nhất, và hoàn thiện bằng insertion sort khi mảng con nhỏ đi. Nói cách khác, nó lấy cùng lúc tốc độ trung bình của quicksort, bảo đảm tệ nhất của heap sort, và hiệu quả quy mô nhỏ của insertion sort.

Thiết kế lai này cho thấy các đánh đổi thấy ở trên được tổng hợp trong thực chiến ra sao. Vì không thuật toán đơn lẻ nào có thể tối ưu trong mọi tình huống, nó chuyển đổi thuật toán một cách động theo kích thước và trạng thái ban đầu của dữ liệu, bảo đảm cùng lúc "hiệu năng trung bình, bảo đảm tệ nhất và tính ổn định". Từ góc nhìn của kỹ sư chuyên nghiệp, khi bàn về sắp xếp phải có khả năng vượt qua việc ghi nhớ độ phức tạp của từng thuật toán để đến với phán đoán thiết kế về việc kết hợp và lựa chọn thuật toán theo yêu cầu.

8. Điểm cần cân nhắc và hàm ý

1. Không có tối ưu tuyệt đối (phù hợp tình huống): Sắp xếp tối ưu thay đổi theo kích thước, trạng thái ban đầu, ràng buộc bộ nhớ và yêu cầu ổn định của dữ liệu. Dữ liệu nhỏ gần như đã sắp xếp hợp với insertion, dữ liệu ngẫu nhiên lớn hợp với quick, và khi cần ổn định thì merge/Timsort là phù hợp.
2. Tránh trường hợp tệ nhất O(n²) của quicksort (độ bền vững): Nên chọn chốt ngẫu nhiên hoặc bằng median-of-three và chuyển sang heap sort khi vượt độ sâu đệ quy (Introsort) để phòng thủ trường hợp tệ nhất. Nếu đối tượng sắp xếp là đầu vào bên ngoài, cần cân nhắc cả khả năng gây ra trường hợp tệ nhất một cách ác ý (tấn công độ phức tạp thuật toán).
3. Nhận diện yêu cầu về tính ổn định (tính đúng đắn): Với công việc cần sắp xếp đa tiêu chí hoặc bảo toàn thứ tự, phải chọn sắp xếp ổn định (merge/Timsort) thay vì quicksort không ổn định thì kết quả mới đúng như ý.
4. Lựa chọn trong môi trường hạn chế bộ nhớ (hiệu quả tài nguyên): Trong môi trường nhúng/quy mô lớn, lượng bộ nhớ bổ sung sử dụng là mấu chốt. Người ta phân biệt giữa sắp xếp tại chỗ (quick, heap) và sắp xếp ngoài (merge dựa trên đĩa) theo việc dữ liệu có nạp vừa bộ nhớ hay không.
5. Tin cậy và kiểm chứng thư viện (nguyên tắc thực tiễn): Trừ khi có lý do đặc biệt, dùng một thư viện chuẩn đã được kiểm chứng (Timsort, Introsort) là an toàn. Cài đặt tự viết dễ có lỗi ở các trường hợp biên, trùng lặp và tệ nhất, nên chỉ cân nhắc cài đặt tối ưu hóa khi yêu cầu hiệu năng rõ ràng.

Tài liệu tham khảo

• Cormen et al., "Introduction to Algorithms", MIT Press (chia để trị, cận dưới của sắp xếp)
• Mô tả CPython Timsort listsort: https://github.com/python/cpython/blob/main/Objects/listsort.txt
• cppreference std::sort (Introsort): https://en.cppreference.com/w/cpp/algorithm/sort

---

Tóm tắt một câu: Bubble sort và insertion sort là các sắp xếp đơn giản O(n²) (insertion hiệu quả một cách thích nghi trên dữ liệu gần như đã sắp xếp), còn quicksort là chia để trị ở mức trung bình O(n log n) nhanh nhưng tệ nhất O(n²) tùy chốt; mấu chốt là phán đoán thiết kế chọn merge sort hoặc một sắp xếp lai (Timsort, Introsort) theo tính ổn định, đặc tính dữ liệu và ràng buộc bộ nhớ.