2
$\begingroup$

I seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is $O(\log n)$. Give an $O(n \log \log n)$ worst-case time algorithm to sort such sequences. I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a deterministic algorithm for the problem described.

It is from the book Algorithm Design Manual by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Please provide proper attribution for the source of this problem. Also, what did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. If the only thing you've tried is checking whether some existing algorithm already happens to suffice, you probably haven't tried enough before asking: you might need to design a new algorithm of your own. $\endgroup$ – D.W.♦ Jan 4 '17 at 0:36
  • $\begingroup$ Hint: The problem with Hoare's original quicksort is that it doesn't handle ranges of equal keys the way you'd hope. How could you fix that? $\endgroup$ – Pseudonym Jan 24 '17 at 6:31
  • $\begingroup$ @ Pseudonym I am not able to understand what do you mean by "ranges of equal keys" . Did you mean when all keys are same ? I know there is a Randomized quick-sort but I am looking deterministic algorithm. $\endgroup$ – aaag Jan 24 '17 at 11:42
  • $\begingroup$ I mean when there are a significant number of equal keys. When the entropy of the key distribution is $o(\log n)$. $\endgroup$ – Pseudonym Jan 24 '17 at 12:29
7
$\begingroup$

How much time does it take to make $\Theta(n)$ queries in a Red-Black Tree with size $O(\log n)$ ?

A detailed solution follows:

Let $T$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $A[i]$ of the original array, query $T$ for a node which first element is $A[i]$. If there is no such node, insert a new node $(A[i], 1)$; otherwise, update the node $(A[i], m)$ with $(A[i], m+1)$.

After you are done with all the elements in A, clear $A$ and visit $T$ in-order. For each node $(x, m)$ of $T$, append $m$ copies of $x$ to $A$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $T$ is $O(\log n)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I don't have any idea about Red-Black Trees. $\endgroup$ – aaag Dec 27 '16 at 18:52
  • 4
    $\begingroup$ You may use any kind of height-balanced search tree instead. Have you heard about AVL trees? 2-3 trees? B/B+/B* trees? $\endgroup$ – quicksort Dec 27 '16 at 18:55
  • $\begingroup$ what is the space complexity of your algorithm? Is it O (log n) ? $\endgroup$ – aaag Jan 24 '17 at 10:59
  • 1
    $\begingroup$ @Shivd Yes. We read the input but never modify it, therefore the space complexity equals the additional space, which is proportional to the size of the tree. $\endgroup$ – quicksort Jan 24 '17 at 11:22
  • $\begingroup$ This answer describes, in fact, an algorithm that sorts $n$ integers in time-complexity $O(n\log k)$ and working-space-complexity $O(k)$, where $k$ is the number of distinct elements, $k\gt1$. $\endgroup$ – Apass.Jack Jun 25 at 12:07
1
$\begingroup$

You don't do any sorting at all. Instead, you make one pass through the array S, collecting all unique values into a sorted array U, and for each unique value create a linked list of the indices of all items with that value.

Since U has a size O (log n), you can lookup any value in time O (log log n) using binary search. You do that n times, so O (n log log n) operations. Modifying array U is O (log^2 n) at most. Then creating the sorted array is O (n). Total O (n log log n).

If the number of unique values f (n) is larger you'll need something more clever than a simple sorted array (f (n) ≥ $O ((n log n)^{1/2})$ to do the job in O (n log f (n)).

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ How do you get from $O(log² n)$ for inserting in the sorted array to Total $O(n\ log\ log\ n)$? $\endgroup$ – greybeard Dec 28 '16 at 7:58
  • $\begingroup$ O(log^2 n) is muck less than O(n). $\endgroup$ – gnasher729 Dec 28 '16 at 16:29
  • $\begingroup$ I still think there is an n missing in You do [lookup] n times, so O (log log n) operations. $\endgroup$ – greybeard Dec 28 '16 at 18:36
  • $\begingroup$ What about space complexity ? Is it $O(\log n)$ ? $\endgroup$ – aaag Jan 18 '17 at 15:00
  • 1
    $\begingroup$ "Modifying array U is O (log^2 n) at most" -- how do you insert into the middle of an array in sublinear time? (Clearly, arrays are worst than balanced BSTs here.) $\endgroup$ – Raphael♦ Jan 24 '17 at 18:44

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.