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?

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 13, 2015 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
    Commented Nov 13, 2015 at 13:17
  • 1
    $\begingroup$ It's a "project algorithm". Isn't a project a kind of assignment? $\endgroup$
    – Yuval Filmus
    Commented Nov 13, 2015 at 13:19
  • $\begingroup$ Ohh, I could also write invent, come up with.... It is only word. $\endgroup$
    – user40545
    Commented Nov 13, 2015 at 13:20

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
4
  • $\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
    Commented Nov 13, 2015 at 17:00
  • $\begingroup$ Quicksort is often considered in-place despite having the same performance. $\endgroup$
    – Yuval Filmus
    Commented Nov 13, 2015 at 21:38
  • $\begingroup$ @user40545 Wouldn't just indexing into the array require $\mathcal O(\lg n)$ memory? $\endgroup$
    – wchargin
    Commented Oct 29, 2016 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
    Commented Oct 30, 2016 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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