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.

$\endgroup$
4
  • $\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.
    Commented Jan 4, 2017 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
    Commented Jan 24, 2017 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$
    – user35837
    Commented Jan 24, 2017 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
    Commented Jan 24, 2017 at 12:29

2 Answers 2

6
$\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)$.

$\endgroup$
5
  • $\begingroup$ I don't have any idea about Red-Black Trees. $\endgroup$
    – user35837
    Commented Dec 27, 2016 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
    Commented Dec 27, 2016 at 18:55
  • $\begingroup$ what is the space complexity of your algorithm? Is it O (log n) ? $\endgroup$
    – user35837
    Commented Jan 24, 2017 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
    Commented Jan 24, 2017 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$
    – John L.
    Commented Jun 25, 2019 at 12:07
0
$\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)).

$\endgroup$
6
  • 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
    Commented Dec 28, 2016 at 7:58
  • $\begingroup$ O(log^2 n) is muck less than O(n). $\endgroup$
    – gnasher729
    Commented Dec 28, 2016 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
    Commented Dec 28, 2016 at 18:36
  • $\begingroup$ What about space complexity ? Is it $O(\log n)$ ? $\endgroup$
    – user35837
    Commented Jan 18, 2017 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
    Commented Jan 24, 2017 at 18:44

Your Answer

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