Quickselect with Hoare partition


  • 0
    P

    Two types of partition exist for quicksort/quickselect. Hoare and Lomuto. Their efficiency is discussed here. Following is an implementation of quickselect using Hoare partition.

    int partition(vector<int>& nums, int st, int ed) {
        if(st >= ed) return st;
        int i(st-1), j(ed+1), pvt(nums[st]);
        while(1) {
            while(nums[++i] > pvt);
            while(nums[--j] < pvt);
            if(i < j) swap(nums[i], nums[j]);
            else return j;
        }
        return j;
    }
    
    int helper(vector<int>& nums, int i, int j, int k) {
        if(i == j) return nums[i];
        int pvt = partition(nums, i, j);
        if(pvt < k) return helper(nums, pvt+1, j, k);
        return helper(nums, i, pvt, k);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return helper(nums, 0, nums.size()-1, k-1);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.