K-th Smallest Element Using Quickselect Algorithm

You are given an unsorted array of n integers and a positive integer k. Your task is to find the k^th smallest element in the array.

The optimal solution is to use the Quickselect algorithm, which is based on the partitioning method of QuickSort. The algorithm typically achieves an average time complexity of \(O(n)\). In this problem, you are required to implement this method.

Input Format: The input is read from standard input (stdin) and consists of the following lines:

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers denoting the elements of the array.
• The third line contains an integer \(k\), representing which smallest element to retrieve (1-indexed).

Output Format: Output a single integer to standard output (stdout), the k-th smallest element in the array.

inputFormat

Input is provided via standard input. The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers. The third line contains an integer \(k\), indicating the order (1-indexed) of the smallest element to find.

outputFormat

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

6
3 2 1 5 6 4
2

2