Given a list of n number A[r..n]. Design an algorithm to find the k-th smallest number in A, where k is part of the input. Furthermore, k is an integer and lies in [1, n]. For example, let Al[1.7]-(-1, 3,-9,2,7,5, 11. If k-3, your algorithm will return 2, which is the third smallest number in A. If k-6, it will return 7, which is the 6-th smallest number in A. One straightforward solution is to first sort A in ascending order and then return Ak. Please design a different algorithm that doesn't require sorting A first. Describe your solution with the following three parts: Input . Output Algorithm: in pseudo code with concise comments