anmol065
anmol065

Reputation: 41

Finding kth smallest element in array using QuickSelect. Why we should substract L(leftmost index) from POS(position of random partition)?

// function for finding Kth smallest element
int kthSmallest(int arr[], int l, int r, int k)
{
    if (k > 0 && k <= r - l + 1)
    {
        int pos = randPart(arr, l, r); // position of random partition
        // now compairing pos with Kth position
        if (pos == k - 1)
            return arr[pos];
        else if (pos > k - 1)
            return kthSmallest(arr, l, pos - 1, k);
        return kthSmallest(arr, pos + 1, r, k);
    }
    return INT_MAX;
}

It gives random output:

PS C:\Users\anmol\Desktop\c++projectwork> g++ .\450\3.-KthMinOrMaxEle.cpp
PS C:\Users\anmol\Desktop\c++projectwork> ./a
enter n and k:
6 3
enter array elements:
7 10 4 3 20 15
answer element:2147483647

The above is my code but solution code has some difference. Solution code is as:

int kthSmallest(int arr[], int l, int r, int k){
    if (k > 0 && k <= r - l + 1){
        int pos = randPart(arr, l, r); // position of random partition
        if (pos - l == k - 1){ // pos-l not pos why?
            return arr[pos];
        }
        else if (pos - l > k - 1)
            return kthSmallest(arr, l, pos - 1, k);
        return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
    }
    return INT_MAX;
}

Why my code is not working because i think randomPartition function(randPart()) return pos index according to orignal array indexing and k-1 is also according to orignal array indexing, So why there is need to convert them?

Upvotes: 0

Views: 153

Answers (0)

Related Questions