Randomized-select kth largest element

Question

I have been studying algorithms recently, and got to the randomized select algorithm. Im trying to figure it out, and stumbled upon this website

https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/

Which shows a code, with little to no explanation of how it works.

It works to find the kth smallest element, but how could it be changed in order to show the kth largest element?

Particularly on this method

    int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];

        // If position is more, recur for left subarray
        if (pos-l > k-1)
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return Integer.MAX_VALUE;
}

to show the kth largest element? Just seek length-k-th smallest — MBo

Schidu Luca Schidu Luca · Accepted Answer · 2018-04-11T17:18:01

You don't have to modify this method kthSmallest. Instead you should modify method partition (taken from the link you provided):

int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] >= x)
        {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, r);
    return i;
}

I changed here the if statement : if (arr[j] <= x) to if (arr[j] >= x)

Randomized-select kth largest element

1 Answers