K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time) - GeeksforGeeks
Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.
The idea is to randomly pick a pivot element. To implement randomized partition, we use a random function, rand() to generate index between l and r, swap the element at randomly generated index with the last element, and finally call the standard partition process which uses last element as pivot.
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
(pos-l > k-1)
// If position is more, recur for left subarray
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
INT_MAX;
}
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], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]);
return
i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] arount the randomly picked element using partition()
int
randomPartition(
int
arr[],
int
l,
int
r)
{
int
n = r-l+1;
int
pivot =
rand
() % n;
swap(&arr[l + pivot], &arr[r]);
return
partition(arr, l, r);
}
The worst case time complexity of the above solution is still O(n2). In worst case, the randomized function may always pick a corner element. The expected time complexity of above randomized QuickSelect is Θ(n), see CLRS book or MIT video lecture for proof. The assumption in the analysis is, random number generator is equally likely to generate any number in the input range.
Read full article from K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time) - GeeksforGeeks