3

The problem at hand is whats in the title itself. That is to give an algorithm which sorts an n element array with O(logn) distinct elements in O(nloglogn) worst case time. Any ideas?

Further how do you generally handle arrays with multiple non distinct elements?

Improve this question
3
  • is the sort meant to be stable? stable means that non-distinct items appear in the output in the same order as they appeared in the input. Commented Aug 31, 2011 at 17:04
  • @Dan, do you have any inherently non-stable solution in mind? I'm curious; please post a hint. Commented Aug 31, 2011 at 18:35
  • Nope this is not homework. I got the question from Algorithm Design Manual..and I have been trying for a day!... No it need not tbe stable! Commented Sep 1, 2011 at 4:33

3 Answers 3

Reset to default
11

O(log(log(n))) time is enough for you to do a primitive operation in a search tree with O(log(n)) elements.

Thus, maintain a balanced search tree of all the distinct elements you have seen so far. Each node in the tree additionally contains a list of all elements you have seen with that key.

Walk through the input elements one by one. For each element, try to insert it into the tree (which takes O(log log n) time). If you find you've already seen an equal element, just insert it into the auxiliary list in the already-existing node.

After traversing the entire list, walk through the tree in order, concatenating the auxiliary lists. (If you take care to insert in the auxiliary lists at the right ends, this is even a stable sort).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I was thinking along the same waybut couldnt proceed. My thought procedure was as follows: 1) Divide the n element list into parts having logn elements 2) Sort each of those parts - nlog(logn) time 3) If I want to search in any of those sorted parts, it will take me O(loglogn) time. Hence searching for n elements(which I do not know what they are at the beginning) will take me O(nloglogn) elements. What next?
I've extended my hint to a full answer.
0

Simple log(N) space solution would be:

find distinct elements using balanced tree (log(n) space, n+log(n) == n time)
Than you can use this this tree to allways pick correct pivot for quicksort.

I wonder if there is log(log(N)) space solution.

Improve this answer

3 Comments

How do you represent the partitions in quicksort in logarithmic space?
Partitions are done inplace. But becuase you know both termination condition and optimal pivot, you can do at most log(log(n)) partitions in depth, and log(n) in total.
In-place? That would seem to require O(n) space. (Usually when one speaks about sublinear space bounds, it is implicit that the input is read-only).
0

Some details about using a tree:

You should be able to use a red black tree (or other type of tree based sorting algorithm) using nodes that hold both a value and a counter: maybe a tuple (n, count).

When you insert a new value you either create a new node or you increment the count of the node with the value you are adding (if a node with that value already exists). If you just increment the counter it will take you O(logH) where H is the height of the tree (to find the node), if you need to create it it will also take O(logH) to create and position the node (the constants are bigger, but it's still O(logH).

This will ensure that the tree will have no more than O(logn) values (because you have log n distinct values). This means that the insertion will take O(loglogn) and you have n insertions, so O(nloglogn).

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.