C++

Use Quick Select (without recursion) to compute the 25% , 50%, and 75% of a data file.

The numbers in the file data.txt are all non-negative integers. The first number of the file, say n, states how many numbers follow. The next n lines all contain a single number. Compute the percentiles of these n numbers (not including n itself). Wirte your program in such a way that the file can contain more than n + 1 lines and still works correctly (i. e., computes the percentile of the n given numbers).

Methods to use NO RECURSION OR FLOATS in this solution

he p-th percentile of a set S is the smallest element e in S such that at least p % of the elements in S (including e) are smaller than or equal to e. To compute the p-th percentile, implement a function int percentile(int p, int S[], int size) which takes a percentage-value p and a (potentially unsorted) array S as input and returns the corresponding percentile. Your implementation must work for any p with 0 p100 (not just 25, 50, and 75).

Your implementation of quickselect has to be non-recursive. Write a helper function inline int ceilDiv(int p, int q) that returns p/q (it is usefull to convert a percentile into an index). Recall that you are NOT ALLOWED TO USE FLOATS. DO NOT SORT THE ARRAY. NO RECURSION; your program should run in O(n) (expected) time.

6 12 67 13 20 61 86 12 13 20 61 67 86 1 2 3 4 5 5 6 6 1 2 3 4 5