Thuật toán Quickselect
Để tìm giá trị lớn thứ k của một mảng, ta có thể sử dụng thuật toán Quickselect, một biến thể của thuật toán QuickSort.
Thuật toán Quickselect hoạt động như sau:
- Chọn một phần tử pivot bất kỳ trong mảng.
- Phân hoạch mảng thành hai phần: các phần tử có giá trị lớn hơn pivot và các phần tử có giá trị nhỏ hơn pivot.
- So sánh số lượng phần tử của phần tử lớn hơn pivot với k:
- Nếu số lượng phần tử lớn hơn pivot bằng k, pivot chính là giá trị lớn thứ k của mảng.
- Nếu số lượng phần tử lớn hơn pivot lớn hơn k, tiếp tục thực hiện Quickselect trên phần tử lớn hơn pivot.
- Nếu số lượng phần tử lớn hơn pivot nhỏ hơn k, tiếp tục thực hiện Quickselect trên phần tử nhỏ hơn pivot.
- Lặp lại quá trình đến khi tìm được giá trị lớn thứ k.
Độ phức tạp của thuật toán Quickselect trung bình là O(n), tuy nhiên trong trường hợp xấu nhất có thể lên đến O(n^2). Tuy nhiên, với một mảng lớn, việc tìm giá trị lớn thứ k bằng Quickselect vẫn nhanh hơn so với việc sắp xếp mảng hoàn toàn rồi lấy phần tử ở vị trí k.
Cài đặt thuật toán Quickselect với Python
import random
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
lows = [el for el in arr if el < pivot]
highs = [el for el in arr if el > pivot]
pivots = [el for el in arr if el == pivot]
if k < len(highs):
return quickselect(highs, k)
elif k < len(highs) + len(pivots):
return pivots[0]
else:
return quickselect(lows, k - len(highs) - len(pivots))
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 2
result = quickselect(arr, len(arr) - k)
print(result)
Cài đặt thuật toán Quickselect với C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;
int quickselect(vector<int>& arr, int k) {
if (arr.size() == 1) {
return arr[0];
}
default_random_engine gen;
uniform_int_distribution<int> dist(0, arr.size() - 1);
int pivot = arr[dist(gen)];
vector<int> lows, highs, pivots;
for (int el : arr) {
if (el < pivot) {
lows.push_back(el);
} else if (el > pivot) {
highs.push_back(el);
} else {
pivots.push_back(el);
}
}
if (k < highs.size()) {
return quickselect(highs, k);
} else if (k < highs.size() + pivots.size()) {
return pivots[0];
} else {
return quickselect(lows, k - highs.size() - pivots.size());
}
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 2;
int result = quickselect(arr, arr.size() - k);
cout << result << endl; // Kết quả sẽ là 6
return 0;
}