📈 Thuật toán sắp xếp

Nếu chỉ cần sắp xếp một mảng, hầu như mọi ngôn ngữ đều có hàm sort() sẵn - vậy tại sao vẫn cần học hàng chục thuật toán sắp xếp khác nhau? Vì không có thuật toán nào thắng tuyệt đối trên mọi tiêu chí; hiểu đánh đổi giữa chúng giúp bạn chọn đúng công cụ, và đây cũng là “phòng thí nghiệm” tốt nhất để luyện tư duy độ phức tạp.

Bốn tiêu chí đánh giá

Trước khi so sánh các thuật toán, cần biết đo chúng bằng thước nào:

Thời gian: độ phức tạp Big O của số phép so sánh/di chuyển.
Tại chỗ (in-place): có cần cấp phát mảng phụ hay không - sắp xếp in-place chỉ tốn O(1) bộ nhớ phụ trội.
Ổn định (stable): hai phần tử bằng nhau có giữ nguyên thứ tự tương đối sau khi sắp xếp không? Tính ổn định quan trọng khi sắp xếp nhiều tầng - ví dụ đã sắp theo tên, giờ sắp tiếp theo tuổi, sắp xếp không ổn định có thể làm xáo trộn thứ tự tên đã có.
Thích ứng (adaptive): thuật toán có chạy nhanh hơn khi dữ liệu đầu vào đã gần như có thứ tự sẵn không?

Không thuật toán nào đạt điểm tối đa ở cả bốn tiêu chí cùng lúc - đó chính là lý do tồn tại nhiều lựa chọn.

Nhóm O(n²): đơn giản nhưng chỉ hợp dữ liệu nhỏ

Selection sort - mỗi vòng tìm phần tử nhỏ nhất trong phần chưa sắp xếp, đưa nó về đúng vị trí. Luôn tốn đúng n-1 lần swap dù dữ liệu đã sắp sẵn hay chưa → không thích ứng.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if arr[j] < arr[k]:
                k = j
        arr[i], arr[k] = arr[k], arr[i]

Bubble sort - liên tục so sánh và hoán đổi hai phần tử liền kề, đẩy dần phần tử lớn nhất về cuối. Nếu thêm một cờ “đã có swap nào chưa” để dừng sớm khi mảng đã sắp xếp, bubble sort trở thành thuật toán thích ứng, đạt O(n) ở trường hợp tốt nhất.

Insertion sort - giống cách bạn sắp một bộ bài trên tay: lấy từng lá bài, chèn nó vào đúng vị trí trong phần đã sắp xếp. Về lý thuyết cũng O(n²), nhưng trong thực tế thường nhanh hơn hai thuật toán trên vì mỗi bước chỉ cần dịch chuyển (assignment), không cần swap 3 bước như bubble sort - đây là lý do nhiều ngôn ngữ dùng insertion sort cho các đoạn mảng nhỏ ngay bên trong cài đặt quick sort/merge sort của họ.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        base = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > base:
            arr[j + 1] = arr[j]   # dịch phải, không swap
            j -= 1
        arr[j + 1] = base

Nhóm chia để trị: O(n log n)

Merge sort - chia mảng làm đôi đệ quy đến khi còn 1 phần tử (luôn có thứ tự), rồi trộn (merge) từng cặp mảng con đã sắp xếp lại với nhau. Việc trộn hai mảng đã sắp xếp chỉ tốn O(n) (duyệt song song, luôn lấy phần tử nhỏ hơn), và có log n tầng chia → tổng O(n log n). Ưu điểm hiếm có: ổn định và có hiệu năng đảm bảo trong mọi trường hợp - không có worst-case tệ. Đánh đổi: cần mảng phụ để trộn, nên không in-place, tốn O(n) bộ nhớ.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

Quick sort - chọn một phần tử làm chốt (pivot), phân hoạch mảng thành “nhỏ hơn pivot” và “lớn hơn pivot” ngay tại chỗ, rồi đệ quy trên từng phần. Khác với merge sort (chia đều rồi mới xử lý), quick sort “xử lý trong lúc chia” - đây là lý do nó in-place (không cần mảng phụ). Trung bình O(n log n) và thường nhanh hơn merge sort trong thực tế nhờ ít di chuyển dữ liệu hơn, nhưng có worst-case O(n²) nếu pivot luôn rơi vào giá trị nhỏ nhất/lớn nhất (ví dụ mảng đã sắp xếp sẵn mà luôn chọn phần tử đầu làm pivot) - đây là lý do cài đặt thực tế thường chọn pivot ngẫu nhiên hoặc theo “median of three” để tránh trường hợp xấu.

Heap sort - dùng chính cấu trúc heap đã học: xây một max-heap từ mảng (O(n)), sau đó liên tục lấy phần tử lớn nhất ra khỏi heap và đặt vào cuối mảng (O(log n) mỗi lần, lặp n lần). Đảm bảo O(n log n) ở mọi trường hợp (không có worst-case tệ như quick sort) và in-place, nhưng không ổn định.

Nhóm không so sánh: nhanh hơn O(n log n), có điều kiện

Về mặt lý thuyết, O(n log n) là giới hạn dưới cho mọi thuật toán sắp xếp dựa trên so sánh cặp phần tử. Nhưng nếu biết trước dữ liệu có tính chất đặc biệt, ta có thể sắp xếp mà không cần so sánh từng cặp, đạt O(n):

Counting sort - nếu dữ liệu là số nguyên trong một khoảng nhỏ đã biết trước, đếm số lần xuất hiện của mỗi giá trị vào một mảng đếm, rồi dựng lại mảng đã sắp xếp từ mảng đếm đó.
Bucket sort - chia dữ liệu vào nhiều “xô” (bucket) theo khoảng giá trị, sắp xếp riêng từng xô nhỏ (thường bằng insertion sort), rồi nối các xô lại. Hiệu quả khi dữ liệu phân bố đều.
Radix sort - sắp xếp số nguyên theo từng chữ số, từ hàng đơn vị đến hàng cao nhất (mỗi lượt dùng counting sort ổn định), không cần biết trước khoảng giá trị lớn cỡ nào - chỉ cần biết số chữ số tối đa.

Cả ba đều đánh đổi tính tổng quát để lấy tốc độ: chúng chỉ hoạt động đúng với dữ liệu có cấu trúc phù hợp (số nguyên trong khoảng nhỏ, hoặc phân bố đều), không sắp xếp được dữ liệu tùy ý như chuỗi so sánh từ điển phức tạp.

Bảng so sánh tổng hợp

Thuật toán	Thời gian (trung bình)	Thời gian (xấu nhất)	Bộ nhớ	Ổn định	In-place
Selection sort	O(n²)	O(n²)	O(1)	Không	Có
Bubble sort	O(n²)	O(n²)	O(1)	Có	Có
Insertion sort	O(n²)	O(n²)	O(1)	Có	Có
Merge sort	O(n log n)	O(n log n)	O(n)	Có	Không
Quick sort	O(n log n)	O(n²)	O(log n)	Không	Có
Heap sort	O(n log n)	O(n log n)	O(1)	Không	Có
Counting/Radix sort	O(n)	O(n)	O(n)	Có	Không