1) Suppose that you need to "approximately sort" arrays of length n, in the sense that if the ith smallest element of the input is at index j in the output, then | i j | k, for some fixed number k (small compared to n). Describe an efficient algorithm and characterize the asymptotic running time (state whether your analysis is worst case or average-case). ( Make a pseudocode for it if you can)