(W3) Divide and Conquer

Question 1

How to find the k closest elements to the median in an unordered sequence - within O(N)

Answer 1

use QuickSelect to find the median

For the remaining numbers, convert them to the absolute difference to the median

then find the k-smallest number, and all numbers between 0 and k-smallest number are your actual values

Question 2

Can you use the average as the pivot for QuickSort? Give a counter example

Answer 2

No - there are situations where this will be horribly inefficient

Take the sequence n! - the average (n!/n), will be (n-1)! - therefore only a single value will be larger than the average (and therefore the pivot). Hence, this will result in O(n^2) runtime

Question 3

How to think of QuickSelect in terms of finding values?

Answer 3

It’s the percentile. If you want the 60th percentile then you want the 6/10-th smallest element