Reference no: EM131230048

Given a sorted array of 100 scores, the quartiles are at index 25, 50, and 75, which divide the data into even rankings each of which are the bottom, 2 middle, and top 25% of all scores. Write an algorithm with expected running time of O(n) that, given an array A of distinct scores NOT sorted, returns an array in which elements A[1] to A[n/4] are the bottom 25%, A[3/4n+1] to A[n] are the top 25%, etc., but the scores are not necessarily sorted within their respective ranking group. HINT: Consider QuickSort and see Randomized-Select(A,p,r,i) in Chapter 9, which can find the ith order statistic (i.e. the ith-smallest element) in the subarray A[p] to A[r]. Briefly justify the runtime.