1
$\begingroup$

An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$.
Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$.
We assume that $k < \sqrt{n}$ - otherwise $O(n\log k) = O(n\log n)$ - then we may use HeapSort.

We may assume that we know $k$. I try to do it. The only thing that I can do is finding all $k$ distinct elements and bring them on beginning of array in $O(n\log k)$ - I use binary search.

However I have no idea how to solve it. Any ideas?

$\endgroup$
  • 1
    $\begingroup$ If it's an assignment then perhaps it's best if you solved it on your own. Are other students also getting outside help? $\endgroup$ – Yuval Filmus Nov 13 '15 at 13:14
  • $\begingroup$ No it isn't assigment. I tried to solve it but I got stuck. I said what I managed to come up with. Clue will be sufficient. $\endgroup$ – user40545 Nov 13 '15 at 13:17
  • 1
    $\begingroup$ It's a "project algorithm". Isn't a project a kind of assignment? $\endgroup$ – Yuval Filmus Nov 13 '15 at 13:19
  • $\begingroup$ Ohh, I could also write invent, come up with.... It is only word. $\endgroup$ – user40545 Nov 13 '15 at 13:20
3
$\begingroup$

Here is an idea. Use a variant of quicksort with a twist:

  1. Find the median $m$ in-place in time $O(n)$ (this could jumble the array).
  2. Partition the array around $m$ using the quicksort partition routine.
  3. Divide the array into three parts: smaller than $m$, equal to $m$, and larger than $m$, and recurse on the first and the last.

Consider a recursion tree for this algorithm. The tree has depth $\log n$ and $k$ nodes. Imagine "compressing" the tree by short-circuiting all nodes having only one child. You get a tree with depth $\log k$. Can you justify this short-circuiting and prove a running time of $O(n\log k)$? Or is there a counterexample?

$\endgroup$
  • $\begingroup$ It's ok, but you use additional space $O(\log k)$ (recursion). Algorithm have should worked in place (constant memory). Let's note that you didn't use fact that $k < \sqrt{n}$ $\endgroup$ – user40545 Nov 13 '15 at 17:00
  • $\begingroup$ Quicksort is often considered in-place despite having the same performance. $\endgroup$ – Yuval Filmus Nov 13 '15 at 21:38
  • $\begingroup$ @user40545 Wouldn't just indexing into the array require $\mathcal O(\lg n)$ memory? $\endgroup$ – wchargin Oct 29 '16 at 22:44
  • 1
    $\begingroup$ @wchargin We are counting machine words rather than bits. Each machine word holds $O(\log n)$ bits. $\endgroup$ – Yuval Filmus Oct 30 '16 at 0:05

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.