Problem Description: Given an array A[] of n elements and a positive integer K, find the Kth smallest element in the array. It is given that all array elements are distinct.
For Example:
Example 1
Input : A[] = {10, 3, 6, 9, 2, 4, 15, 23}, K = 4
Output: 6
Example 2
Input : A[] = {5, -8, 10, 37, 101, 2, 9}, K = 6
Output: 37
The naive way to find the kth element is to sort the array and get the kth element.
But there is a better solution for finding the kth smallest element and the technique name is quickselect.
From Wikipedia
quickselect is a selection algorithm to find the kth smallest element in an unordered list. It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare’s selection algorithm. Like quicksort, it is efficient in practice and has excellent average-case performance, but has a poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations.
public class KthElement
{
public static int kthElement(int[] arr, int k)
{
int n = arr.Length;
int lo = 0;
int hi = n - 1;
if (lo == hi)
return arr[lo];
while (true)
{
int pivotIndex = Partition(arr, lo, hi);
int rank = pivotIndex - lo + 1;
if (rank == k)
return arr[pivotIndex];
else if (k < rank)
return kthElement(arr, k);
else
return kthElement(arr, k - rank);
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i < j)
{
while (arr[i] <pivot) i++;
while (arr[j] >= pivot) j--;
if (i < j)
Swap(arr, i, j);
}
Swap(arr, left, j);
return j;
}
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}