QuickSelect

Theory

• Quickselect on Wikipedia

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

typedef long long int64;
class QuickSelect {
private:
    int partition(vector<int>& A, int left, int right, int pivotIndex) {
        int pivotValue = A[pivotIndex];
        std::swap(A[pivotIndex], A[right-1]);
        int nextIndex = left;
        for (int i = left; i + 1 < right; i++) {
            if (A[i] < pivotValue) {
                std::swap(A[nextIndex], A[i]);
                nextIndex++;
            }
        }
        std::swap(A[nextIndex], A[right-1]);
        return nextIndex;
    }
    
    int select(vector<int>& A, int left, int right, int k, std::mt19937& gen) {
        if (left + 1 == right) {
            return A[left];
        }
        int size = right - left;
        int64 rnd = static_cast<int64>(gen()) % size;
        int pivotIndex = left + rnd;
        pivotIndex = partition(A, left, right, pivotIndex);
        if (k == pivotIndex + 1) {
            return A[pivotIndex];
        } else if (k < pivotIndex + 1) {
            return select(A, left, pivotIndex, k, gen);
        }
        return select(A, pivotIndex + 1, right, k, gen);
        
    }
public:
    int findKthSmallest(vector<int>& nums, int k) {
        std::random_device rd;
        std::mt19937 gen(rd());
        return select(nums, 0, nums.size(), k, gen);
    }
};

Practice

• https://leetcode.com/problems/kth-largest-element-in-an-array/