Problem 2: On input an array A of n elements, each of which is an integer in (0.
ID: 3750824 • Letter: P
Question
Problem 2: On input an array A of n elements, each of which is an integer in (0.3), describe a simple method for sorting A in O(n) time. Hint: think of alternative ways of viewing the elements Problem 3: Given a set S of n elements its r-percentiles are defined as the values in S that divide the sorted version of S in 10 sets of equal size (plus or minus 1). For example the 20-percentile values are the values that divide the sorted version of S in 5 equal size sets. Example: S 12,3,6,9,15,4, 1, 19,21,8, 13 has n 11 elements. Its sorted version is Sorted S) Describe an algorithm that finds the r-percentiles in O(n log k) time. 1,3,4,6,8,9,12, 13, 15, 19, 21]. The 20-percentiles are (3,6,9, 13,21).Explanation / Answer
The algorithm turns out to be pretty simple -
1) take input the array
2) sort the array
3) calculate the value of K
4) compare length of array with value of K, if the value is greater than length of array then it is impossible else if value is less than equal to length then its possible
5) divide the length of array with value of k to know the steps you need to take at every point i.e. the number of elements you need to skip starting from first element in array. let us denote this value by x.
6) iterate from the starting point in array skipping x-1 element each time and decreasing k by one when you skip an element, also you everytime compare value of k with the remaining length of array, if the value of k less than remaining length then you can continue skipping else if value of k becomes greater than equal to remaining length you stop skipping elements. This entire algorithm is linear in length of array.
7) the complexity of algorithm comes out to be O(nlogk) because only sorting and a for loop of complexity O(n) is involved.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.