Consider the algorithm below, which accepts an array data and an integer r and returns the r^th smallest value in the array

1. Prove that r p must be between 1 and the length of data[p + 1..n], inclusive, when line 14 is executed.

2. Prove that this algorithm returns the r th smallest value in the array. You may assume that all elements of data are unique

Input: data: array of integers Input n: size of data Input r: desired rank to search for: must be between 1 and n inclusive output rth smallest value in data; i.e., a value in data such that exactly r 1 other values are smaller 1 Algorithm: FindRank(data, r) 2 if n 1 then 3 I return data[1] 4 end 5 Let pivot be a randomly selected value in data 6 Partition data into values less than pivot and pivot, as in Quick Sort 7 Insert the pivot in between the "small" and "large" parts of array 8 Let p be the new location of the pivot 9 if r then 10 return pivot 11 else if p r then 12 I return FindRank data 1.p -1], r) 13 else 14 return FindRank (data p 1...n] r p) 15 end