CODEWITHSUNDEEP
algorithmclrsquickselect
Gopalakrishnan Ganesan
Gopalakrishnan Ganesan

Reputation: 9

Quickselect algorithm condition

So I am going through the Quick select algorithm from the CLRS book and I understand the whole concept of the algorithm. But one thing that I am not able to grasp is the initial condition they have at the top. Following is my implementation of the algorithm from the book:

private int quickSelect(int[] arr, int p, int r, int i){
    
    if(r==p){
        return arr[p];
    }

    int q=partition(arr,p,r);

    if(i-1==q){
        return arr[q];
    }
    else if(i-1<q){
        return quickSelect(arr,p,q-1,i);
    }
    else{
        return quickSelect(arr,q+1,r,i);
    }

}

Here, why do we check if p==r and return arr[p]? The value of position i passed might not be the same as p/r. If they give a value higher than the array length, then this would not make sense. Instead of that, it would be better to throw an exception after checking it. I went through a lot of resources on the internet and some of them also use the same condition at the start. QuickSelect Algorithm In this post, it is given that the condition is to check if there is only one element is present but I am not sure how that works.

Upvotes: 0

Views: 202

Answers (0)

Related Questions