Find kth largest element using quick select algorithm

Question

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int partition(vector<int> &nums, int low,int high,int pivotElement)
    {
        int pivotPoint=low;
        for(int i=low;i<=high-1;i++)
        {
            if(nums[i]<=pivotElement)
            {
                swap(nums[i],nums[pivotPoint]);
                pivotPoint++;
            }
        }
        swap(nums[pivotPoint],pivotElement);
        return pivotPoint;
        
    }
    int quickSelect(vector<int> &nums, int k,int low,int high)
    {
        int pivotElement=nums[high];
        int pivot=partition(nums,low,high,pivotElement);
        if(pivot==k)
        {   
            return nums[pivot];
        }
        else if(pivot>k)
            return quickSelect(nums,k,low,pivot-1);
        else
        {   
            return quickSelect(nums,k,pivot+1,high);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
     return quickSelect(nums,nums.size()-k,0,nums.size()-1);
    }
};
int main(){
vector<int> v={3,2,1,5,6,4};
Solution ob;
cout<<ob.findKthLargest(v,2);
}

This is my code, I have used quick select algorithm. In this question i am aimed to get kth largest element. It is giving wrong answer on some test cases though i have tried to cover everything and many test cases are passed. I tried to use cout statement to fetch the error though as per my dry run I should have got correct output. But when I tried to print the elements after first partition though 4 should have moved to index 3 and 5 at last as per swap but that's not happening 4 is still at last and 5 at index 3. I am unable to figure that out. Kindly help me resolve this. I have tried to explain the issue in best way if any further clarification is required would be more than happy to provide. Thank you.

Answer 1

The swap in partition changes the value of the local variable pivotElement, which will not be propogated back to the caller. (You'd get the same effect with nums[pivotPoint] = pivotElement;.)

You need to pass pivotElement by reference, and pass nums[high] directly in order for nums[high] to be updated:

int partition(vector<int> &nums, int low,int high,int &pivotElement)
// ...
// Later, in quickSelect
    int pivot=partition(nums,low,high,nums[high]);