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.

If you're not looking for code, it might be better to go to cs.stackexchange.com. — hgazibara
– hgazibara, Commented Jul 28, 2017 at 7:47

Prateek Mirdha · Accepted Answer · 2017-07-28 09:01:21Z

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......

edited Jul 28, 2017 at 9:01

answered Jul 28, 2017 at 8:42

Prateek Mirdha

676 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mickey Over a year ago

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 Over a year ago

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 Over a year ago

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 Over a year ago

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.

Collectives™ on Stack Overflow

Sorting and Selecting an almost sorted array

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related