Sắp xếp nhanh

9.1 Định nghĩa sắp xếp nhanh

Sắp xếp nhanh (Quick Sort) là một thuật toán sắp xếp hiệu quả, sử dụng phương pháp "chia để trị". Nó hoạt động bằng cách chọn một phần tử làm chốt (pivot), chia mảng thành hai mảng con — các phần tử nhỏ hơn chốt và các phần tử lớn hơn chốt, sau đó áp dụng đệ quy quy trình tương tự cho từng mảng con.

Thuật toán sắp xếp nhanh xuất hiện để giải quyết vấn đề "làm sao chuyển các phần tử nhỏ hơn sang trái càng nhanh càng tốt, và các phần tử lớn hơn sang phải". Giả sử chúng ta có phần tử nhỏ nhất ở cực bên phải, có cách nào để nhanh chóng chuyển nó, nếu không đến vị trí cuối cùng thì cũng gần vị trí đó? Điều này sẽ giúp giảm đáng kể số lượng so sánh không cần thiết.

Nguyên lý hoạt động:

1. Chọn phần tử chốt (pivot):

Chọn một phần tử từ mảng làm chốt. Đó có thể là phần tử đầu tiên, phần tử cuối cùng, phần tử giữa hoặc phần tử ngẫu nhiên. Đôi khi đó là giá trị trung bình của ba phần tử ngẫu nhiên.

2. Phân chia (partitioning):

Di chuyển tất cả các phần tử nhỏ hơn chốt vào phần trái của mảng, và tất cả các phần tử lớn hơn chốt vào phần phải của mảng. Kết quả là phần tử chốt ở đúng vị trí cuối cùng của nó trong mảng đã sắp xếp.

3. Áp dụng đệ quy:

Áp dụng đệ quy quá trình cho các mảng con bên trái và bên phải, không kể phần tử chốt.

Quá trình từng bước

1. Chọn phần tử chốt.
2. Di chuyển các phần tử nhỏ hơn chốt sang trái, và các phần tử lớn hơn sang phải.
3. Áp dụng đệ quy quá trình cho các mảng con.

Độ phức tạp thời gian và không gian của sắp xếp nhanh

Độ phức tạp thời gian:

• Trường hợp xấu nhất: O(n^2) — xảy ra khi mỗi lần chọn phần tử chốt tệ nhất (ví dụ khi mảng đã được sắp xếp).
• Trường hợp trung bình: O(n log n) — cho dữ liệu phân bố ngẫu nhiên.
• Trường hợp tốt nhất: O(n log n) — khi mảng mỗi lần được chia thành các phần bằng nhau.

Độ phức tạp không gian:

O(log n) — cần thiết để lưu trữ stack gọi đệ quy, nếu sử dụng đệ quy đuôi và phần tử chốt được chọn khéo léo.

9.2 Triển khai thuật toán sắp xếp nhanh

Triển khai bằng Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Trường hợp cơ bản: mảng với 0 hoặc 1 phần tử đã được sắp xếp
    
    pivot = arr[len(arr) // 2]  # Chọn phần tử chốt
    left = [x for x in arr if x < pivot]  # Phần tử nhỏ hơn chốt
    middle = [x for x in arr if x == pivot]  # Phần tử bằng chốt
    right = [x for x in arr if x > pivot]  # Phần tử lớn hơn chốt
    
    return quick_sort(left) + middle + quick_sort(right)

# Ví dụ sử dụng:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Mảng đã sắp xếp:", sorted_arr)
# Xuất kết quả: Mảng đã sắp xếp: [1, 1, 2, 3, 6, 8, 10]

Ví dụ hoạt động của thuật toán

Lấy ví dụ mảng: [3, 6, 8, 10, 1, 2, 1]

Lần duyệt đầu tiên:

• Phần tử chốt: 8
• Phần tử trái: [3, 6, 1, 2, 1]
• Phần tử giữa: [8]
• Phần tử phải: [10]

Sắp xếp đệ quy phần bên trái [3, 6, 1, 2, 1]:

• Phần tử chốt: 1
• Phần tử trái: []
• Phần tử giữa: [1, 1]
• Phần tử phải: [3, 6, 2]

Sắp xếp đệ quy phần bên phải [3, 6, 2]:

• Phần tử chốt: 6
• Phần tử trái: [3, 2]
• Phần tử giữa: [6]
• Phần tử phải: []

Sắp xếp đệ quy phần bên trái [3, 2]:

• Phần tử chốt: 2
• Phần tử trái: []
• Phần tử giữa: [2]
• Phần tử phải: [3]

Kết quả hợp nhất: [1, 1, 2, 3, 6] cho phần trái, [10] cho phần phải, và [8] cho phần giữa.

Mảng đã sắp xếp cuối cùng: [1, 1, 2, 3, 6, 8, 10]