Sorting and Selecting an almost sorted array

Question

Given an array of length n where each item has a distance of at most log(n) from its final position in the sorted array, how do I efficiently sort it, and how do I find the k-th valued item (select-k)?

This are my starting ideas:

For sorting, using the comparison model I can get that there are will be approximately O((logn)^n) possible permutations, therefore the max-depth of the comparison tree should be O(nloglogn). Also, for the select problem, I have an intuition that if I look at the range of logn for each side of the k-th item (2logn - 1), I can use a deterministic selection algorithm in O(logn), however I'm not sure about how to prove the correctness of this method.

Please note that I'm not looking for code (in any language), but a sketch of the abstract algorithm and the time complexity for it.

Thanks.

• hgazibara: If you're not looking for code, it might be better to go to cs.stackexchange.com.

Answer 1

Use a minHeap of length

x=log(n)

Start from beginning and push elements to Heap and accordingly after x insertions you will find the smallest element and continue so on to scan other elements.

Complexity -

O(n(log(x))) = x*log(x)(for heap operations for first x elements) + (n-x)(log (x))(for remaining elements)
x=log(n);

You can identify k-th value on your way to sorting by keeping track of how many elements have already sorted......

• Mickey: Great idea with the minHeap. For the k-th value - I want to get better complexity for it, therefore it should be a different algorithm (separated from the sorting), do you have any ideas on that?
• Prateek Mirdha: See if you need to check the kth element then you could only check elements 2*log(n)+1(" say y elements") that is kth element and log(n) elements to left and right of it. After sorting or any other method you could find log(n)+1 th element in these elements, but I think it could take ylog(y)(=log(n)log(log(n))) time i.e for sorting and don't know if it could be done in better time complexity.
• Mickey: There is a deterministic algorithm for seleciton in O(n) time for array of size n. So probably it is O(logn), but I'm not sure why we can discard the other items in the array (which are not at positions 2*log(n)-1), do you have any idea on that? Also, Gave you the upvote and correct answer for the sorting solution, if you can - would love your idea on my question here in the comment. thanks
• Prateek Mirdha: If you take all elements or just 2*log(n)+1 elements the kth position will be occupied by only one element.....so I think other elements will not have any effect on it.