Algorithm: Quick select not returning right answer

I was trying to solve the question "what is the kth largest element of vector nums"

Is a leetcode question.

below is all the code. It should return five. After analyzing the code I noticed that tail=kth element on the second iteration however tail is not at the final destination. Things are only correct if I choose the last element as the pivot but WHY? shouldn't work regardless of pivot selection?

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int kthLargestElement(vector<int> nums, size_t kth)
    {
        return quickSelect(nums, 0, nums.size()-1, nums.size() - kth);
    }
    int quickSelect(vector<int> nums, size_t left, size_t right, size_t kth)
    {
        size_t tail = left, pointer = left, pivot = (left+right)/2;
        while(pointer <= pivot)
        {
            if(nums[pointer] < nums[pivot])
            {
                std::swap(nums[tail], nums[pointer]);
                tail++; pointer++;
            }
            else
                pointer++;
        }
        
        std::swap(nums[tail], nums[pivot]);
        if(tail > kth)
            return quickSelect(nums, left, tail-1, kth);
        else if(tail < kth)
            return quickSelect(nums, tail+1, right, kth);
        return nums[tail];
    }
};

int main()
{
    Solution s;
    auto test = vector<int>{3,2,1,5,6,4};
    cout<< s.kthLargestElement(test, 2)<< endl;
}

Solution

There are a few issues:

Your loop is not visiting the values after the pivot index, yet some of those could be less than the pivot value also, and so this bug affects the result.
Once the previous point is corrected, the tail index will potentially get to the pivot index, and then a swap could move that pivot value to another location. As a consequence the final swap might not swap the pivot, but some other value. To avoid that, the pivot should be moved aside before you start the loop, for instance to the extreme right side. Then we can ensure that after the loop the pivot has not moved, and we can do a controlled swap.

Not a problem, but:

It would be a good idea to pass the vector by reference.
As you increase pointer in each iteration of the loop, you could get rid of the else clause, and use a for loop.

Here is a correction of the quickSelect function

    // Take the vector by reference:
    int quickSelect(vector<int> &nums, size_t left, size_t right, size_t kth)
    {
        size_t tail = left; 
        // Safeguard pivot value, by moving it to the right side
        std::swap(nums[(left + right) / 2], nums[right]); 
        // Visit ALL values (except pivot)
        for (size_t pointer = left; pointer < right; pointer++) 
        {
            if (nums[pointer] < nums[right]) // Pivot is now at the right
            {
                std::swap(nums[tail], nums[pointer]);
                tail++;
            }
        }

        std::swap(nums[tail], nums[right]); // Now we are sure we swap the pivot
        return tail > kth ? quickSelect(nums, left, tail-1, kth)
             : tail < kth ? quickSelect(nums, tail+1, right, kth)
             : nums[tail];
    }