Quick Select (Bầu Cử Sát Thủ K)

O(N) trung bình. Tìm giá trị lớn thứ K bằng độ linh hoạt của Pivot mà không cần tốn O(NlogN) để sort toàn mảng.

Bắt đầu Quick Select để tìm phần tử nhỏ thứ 3 (tức Index = 2 sau khi sort).
🎯 K-Target (Idx 2)
7
[0]
2
[1]
1
K=2
6
[3]
8
[4]
5
[5]
3
[6]
4
[7]
Delay

⚔️ Quick Select

Thay vì sử dụng `O(N log N)` để sắp xếp lại mảng toàn bộ rồi trỏ tới `A[K]`, thuật toán Quick Select đi đường tắt siêu đẳng cấp.

  • Phân hoạch (Partition) bằng một Chốt (Pivot).
  • Phát hiện xem Chốt nằm ở Index số mấy.
  • Giai đoạn tàn nhẫn nhất: Nếu Chốt bé hơn K, nó sẽ VỨT BỎ toàn bộ nửa trái của mảng. Nếu Lớn hơn K, vứt bỏ toàn bộ nửa phải. Không đệ quy 2 bờ như Quick Sort!

Hệ quả: Tốc độ trung bình xé gió đạt `O(N)`. Thuật toán sinh ra để phục vụ Ranking/Leaderboard thời gian thực.