0
$\begingroup$

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time.

The complexity $O(n)$ seems to imply that it is necessary to go through the entire array, but when using a sorting algorithm in the first step of building a tree/heap by using heap sort, this and other $O(nlogn)$ algorithms are the fastest they can be when processing the entire $n$ elements.

Does this mean that I don't have to process all the numbers, and what kind of strategy can I use?

$\endgroup$
  • $\begingroup$ I don't see the problem here, you have an array with m=sqrt(n) elements, so you can sort it in O(m ln m) = O(sqrt(n) ln(n) ) that is under O(n)... did I miss something? $\endgroup$ – Tryss Apr 28 '15 at 3:02
  • $\begingroup$ There are n elements in the array and it's unsorted, and I want to get the first sqrt(n) sorted elements from it. $\endgroup$ – maregor Apr 28 '15 at 3:12
  • $\begingroup$ It's tstill unclear to what you want exactly : do you want to sort the sqrt(n) biggest (or smallest) elements? something else? $\endgroup$ – Tryss Apr 28 '15 at 3:15
  • $\begingroup$ I want to get the first $\sqrt{n}$ elements of its sorted version, so smallest. $\endgroup$ – maregor Apr 28 '15 at 3:18
1
$\begingroup$

I'm not sure it can be done.

First of all, you have to look at all $n$ items.

Then, you have to keep the top $\sqrt{n}$ items. To find where an item that is in the top $\sqrt{n}$ places, you have to do $O(\log(\sqrt{n})) =O(\log(n)) $ comparisons. If the items are badly ordered, you will have to do this $n$ times.

This gives a worst case time of $O(n \log n)$.

If the items are will distributed, the placing in the top $\sqrt{n}$ might only be done $\sqrt{n}$ times. In this case, the placing would only take $O(\sqrt{n}\log(n))$ operations, so this would be $O(n)$.

$\endgroup$
  • $\begingroup$ Is it possible not to look through the entire array but just one half of the array each time such that it adds up to roughly n? This is a homework problem. $\endgroup$ – maregor Apr 28 '15 at 3:27
  • $\begingroup$ I don't think so. You have to look at all elements. Suppose that the items are in decreasing order (assuming that you want the smallest items). Then the items you want are at the end. Do you have to get $O(n)$? $\endgroup$ – marty cohen Apr 28 '15 at 3:31
  • $\begingroup$ Yes, I have to get $O(n)$ $\endgroup$ – maregor Apr 28 '15 at 3:58
  • $\begingroup$ You might take a look at the algorithm for finding the k-th best item. It has a O(n) time for fixed k. If it can be done with $k = \sqrt{n}$ in time O(n), then one additional pass can get the top $\sqrt{n}$ in O(n). $\endgroup$ – marty cohen Apr 28 '15 at 4:12
  • $\begingroup$ Aha! Look up quickselect here: en.wikipedia.org/wiki/Selection_algorithm $\endgroup$ – marty cohen Apr 28 '15 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.