Thuật toán sắp xếp nhanh: cách hoạt động, mã và độ phức tạp

Ý tưởng bằng lời đơn giản

1. Chọn một phần tử pivot, ví dụ phần tử cuối hoặc một phần tử ngẫu nhiên.
2. Phân hoạch: chuyển mọi phần tử nhỏ hơn pivot sang bên trái nó và mọi phần tử lớn hơn sang bên phải. Lúc này pivot đã ở đúng vị trí cuối cùng đã sắp xếp.
3. Sắp xếp đệ quy phần bên trái pivot và phần bên phải pivot. Sau đó không cần kết hợp gì thêm.

Sắp xếp trộn chia dễ nhưng trộn khó. Sắp xếp nhanh ngược lại: việc phân hoạch làm công việc chính, còn nối hai nửa miễn phí vì chúng đã nằm đúng chỗ trong cùng một mảng.

Ví dụ minh họa: một lần phân hoạch Lomuto

Phân hoạch [10, 80, 30, 90, 40, 50, 70] với phần tử cuối, 70, làm pivot. Chỉ số i đánh dấu cuối vùng các phần tử nhỏ hơn pivot; j quét từ trái sang phải.

Giờ 70 nằm ở chỉ số 4, vị trí cuối cùng của nó. Sau đó sắp xếp nhanh sắp xếp riêng [10, 30, 40, 50] và [90, 80].

Cài đặt bằng Python

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

Đệ quy vào phía nhỏ hơn và lặp trên phía lớn hơn giữ độ sâu ngăn xếp ở O(log n) ngay cả trong trường hợp xấu nhất. Một phiên bản ngắn, không tại chỗ, rất phổ biến để giải thích ý tưởng, nhưng nó cấp phát list mới ở mỗi mức:

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

Độ phức tạp thời gian và không gian

Trường hợp xấu nhất kinh điển là pivot cố định ở phần tử đầu hoặc cuối trên đầu vào đã sắp xếp hoặc sắp xếp ngược: mỗi lần phân hoạch chỉ loại được pivot, tạo ra n mức với O(n) công việc. Pivot ngẫu nhiên khiến điều này cực kỳ khó xảy ra với mọi đầu vào.

So sánh sắp xếp nhanh với các thuật toán khác

Sắp xếp nhanh không ổn định: một phép đổi chỗ khi phân hoạch có thể đưa một phần tử vượt qua phần tử bằng nó. Nó thường thắng sắp xếp trộn và sắp xếp vun đống trên mảng trong bộ nhớ vì vòng lặp trong đơn giản, làm việc tại chỗ và truy cập bộ nhớ chủ yếu tuần tự. Introsort, được nhiều bản cài đặt std::sort trong thư viện chuẩn C++ dùng, bắt đầu bằng sắp xếp nhanh và chuyển sang sắp xếp vun đống nếu đệ quy quá sâu, nhờ đó đảm bảo O(n log n).

Lựa chọn pivot, biến thể và lỗi thường gặp

• Lựa chọn pivot: phần tử đầu hoặc cuối (đơn giản, nhưng O(n²) trên đầu vào đã sắp xếp), phần tử ngẫu nhiên, hoặc trung vị của ba (đầu, giữa, cuối).
• Phân hoạch Hoare: hai chỉ số tiến vào nhau và đổi chỗ các cặp nằm sai phía. Trung bình nó đổi chỗ ít hơn Lomuto.
• Phân hoạch ba đường (cờ quốc gia Hà Lan): chia thành nhỏ hơn, bằng và lớn hơn. Nó giúp mảng có nhiều khóa trùng chạy nhanh; Lomuto thuần túy suy giảm thành O(n²) khi mọi khóa bằng nhau.
• Dual-pivot quicksort dùng hai pivot và ba phần; Java dùng nó để sắp xếp mảng kiểu nguyên thủy.
• Quickselect dùng một lần phân hoạch và chỉ đệ quy vào một phía để tìm phần tử nhỏ thứ k trong O(n) trung bình.

Khi nào nên dùng sắp xếp nhanh

Sắp xếp nhanh là lựa chọn mặc định tốt để sắp xếp mảng trong bộ nhớ khi không cần tính ổn định. Trong Python, hãy dùng sorted() hoặc list.sort(); chúng dùng Timsort, ổn định và nhanh trên dữ liệu đã sắp xếp một phần. Cài đặt sắp xếp nhanh là bài phỏng vấn rất phổ biến, thường kèm câu hỏi về trường hợp xấu nhất, cách chọn pivot, tính ổn định, hoặc dùng quickselect để tìm phần tử lớn thứ k.