Sắp xếp nhanh

Khái niệm

Sắp xếp nhanh (quick sort) cũng áp dụng chia để trị, nhưng theo cách khác: chọn một pivot (phần tử chốt), phân hoạch dãy thành hai nhóm (nhỏ hơn pivot và lớn hơn pivot), rồi đệ quy sắp xếp từng nhóm.

Độ phức tạp thời gian:
- Trung bình: O(n log n) — pivot chia đôi dãy đều
- Xấu nhất: O(n²) — pivot luôn là min hoặc max
Độ phức tạp không gian: O(log n) — stack đệ quy
Ổn định: Không

Quick sort nhanh trong thực tế vì tính cache-friendly và hằng số nhỏ, dù cùng ký hiệu O(n log n) với merge sort.

Sơ đồ phân hoạch

graph TD; A["[3,6,8,10,1,2,1] pivot=1"] --> B["Phân hoạch"]; B --> C["[1] < pivot"]; B --> D["[1] == pivot"]; B --> E["[3,6,8,10,2] > pivot"]; C --> F["Đệ quy"]; E --> G["Đệ quy"]; F --> H["[1,1,2,3,6,8,10]"]; D --> H; G --> H;

Cài đặt đơn giản (Lomuto partition)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]   # Chọn pivot ở giữa
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

data = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(data))  # [1, 1, 2, 3, 6, 8, 10]

Cài đặt tại chỗ (in-place) — hiệu quả hơn về bộ nhớ

def quick_sort_inplace(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort_inplace(arr, lo, p - 1)
        quick_sort_inplace(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot = arr[hi]   # Lấy phần tử cuối làm pivot
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

data = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort_inplace(data))  # [1, 1, 2, 3, 6, 8, 10]

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

Dễ — Sắp xếp và lấy phần tử thứ k

Tìm phần tử lớn thứ k trong dãy (k=1 là lớn nhất).

def phan_tu_thu_k_lon_nhat(arr, k):
    """Tìm phần tử lớn thứ k. k=1 là lớn nhất."""
    sorted_arr = quick_sort(arr[:])
    return sorted_arr[-k]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

data = [3, 2, 1, 5, 6, 4]
print(phan_tu_thu_k_lon_nhat(data, 1))   # 6
print(phan_tu_thu_k_lon_nhat(data, 2))   # 5
print(phan_tu_thu_k_lon_nhat(data, 3))   # 4

Trung bình — QuickSelect: Tìm phần tử thứ k trong O(n) trung bình

QuickSelect dùng ý tưởng Quick Sort nhưng chỉ đệ quy một nửa — giảm phức tạp xuống O(n) trung bình.

def quick_select(arr, k):
    """Tìm phần tử nhỏ thứ k (k=0 là nhỏ nhất). O(n) trung bình."""
    if len(arr) == 1:
        return arr[0]

    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    if k < len(left):
        return quick_select(left, k)
    elif k < len(left) + len(mid):
        return pivot
    else:
        return quick_select(right, k - len(left) - len(mid))

data = [3, 1, 4, 1, 5, 9, 2, 6]
print(quick_select(data, 0))   # 1 (nhỏ nhất)
print(quick_select(data, 3))   # 3 (nhỏ thứ 4)
print(quick_select(data, 7))   # 9 (lớn nhất)

Khó — Sắp xếp theo nhiều tiêu chí

Cho danh sách (điểm thi, tên). Sắp xếp giảm dần theo điểm; bằng điểm thì tăng dần theo tên.

def sap_xep_xep_hang(danh_sach):
    """Sắp xếp (diem, ten): giảm dần theo điểm, tăng dần theo tên."""
    return sorted(danh_sach, key=lambda x: (-x[0], x[1]))

# Nếu muốn tự cài bằng quick_sort:
def quick_sort_custom(arr):
    if len(arr) <= 1:
        return arr
    pivot_diem, pivot_ten = arr[len(arr) // 2]
    left  = [(d,t) for d,t in arr if (d > pivot_diem) or (d == pivot_diem and t < pivot_ten)]
    mid   = [(d,t) for d,t in arr if d == pivot_diem and t == pivot_ten]
    right = [(d,t) for d,t in arr if (d < pivot_diem) or (d == pivot_diem and t > pivot_ten)]
    return quick_sort_custom(left) + mid + quick_sort_custom(right)

du_lieu = [(85, "Minh"), (90, "An"), (85, "Cuong"), (90, "Bao")]
for diem, ten in sap_xep_xep_hang(du_lieu):
    print(f"  {ten}: {diem}")
# An  : 90
# Bao : 90
# Cuong: 85
# Minh : 85

Kết luận

Quick sort là thuật toán sắp xếp được dùng nhiều nhất trong thực tế (Python’s timsort, Java’s Arrays.sort đều có nền tảng từ ý tưởng này). Khi n lớn và không cần tính ổn định, quick sort thường là lựa chọn hàng đầu.

Sau khi nắm vững sắp xếp, tiếp tục với các kỹ thuật tối ưu hoá mảng.

Trong series này: