K-th Smallest Element using Quickselect

You are given an array of n integers and a positive integer k. Your task is to find the k-th smallest element in the array using the Quickselect algorithm. The Quickselect method is an efficient selection algorithm to find the k-th smallest element in an unordered list, inspired by the partition method used in Quicksort.

The algorithm works by selecting a pivot element and partitioning the array such that elements less than or equal to the pivot are moved to one side and the rest to the other side. Recursively, the algorithm then focuses on the partition that contains the desired element until it is found.

The theoretical time complexity of Quickselect is on average \(O(n)\), although in the worst case it can degrade to \(O(n^2)\). However, with a good pivot selection strategy, it performs extremely well in practice.

inputFormat

The input is given via standard input and consists of two lines:

• The first line contains two integers n and k (\(1 \leq k \leq n\)), where n is the number of elements in the array.
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the k-th smallest element from the given array to the standard output.

6 3
7 10 4 3 20 15

7