CODEWITHSUNDEEP
algorithmsorting
Adwaitvedant
Adwaitvedant

Reputation: 253

Sorting an n element array with O(logn) distinct elements in O(nloglogn) worst case time

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?

Upvotes: 3

Views: 6102

Answers (3)

hmakholm left over Monica
hmakholm left over Monica

Reputation: 23332

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).

Upvotes: 11

andredor
andredor

Reputation: 552

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).

Upvotes: 0

Luka Rahne
Luka Rahne

Reputation: 10457

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.

Upvotes: 0

Related Questions