Случайный быстрый выбор не работает для тех же значений ⇐ C++

[Anonymous]

Я пробую следующее решение для быстрого выбора в C++, но оно не работает для большого массива с k=50000.

Код: Выделить всё

class Solution {
public:
int partition(vector& A, int p, int r) {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution distr(p, r);
int pivot = distr(gen);
swap(A[pivot], A[r]);

int x = A[r];
int i = p - 1;
for (int j=p; j  со средними значениями 1 (и k=50000) я получаю сообщение об ошибке превышения лимита времени. 

Подробнее здесь: [url]https://stackoverflow.com/questions/79225213/randomized-quickselect-failing-for-same-values[/url]