The most useful data structure would be BST.
Each node will have data value and its count. count indicates the number of
times it is repeated in a sequence. Below is the algo to creat a binary
search tree.
insert_node(int data, node root)
{
if(root == NULL)
{
root = malloc();
root->right = NULL;
root->left = NULL;
root->data = data;
root->count =1;
}
else if(root->data == data)
{
root->count++;
}
else if(data < root->data)
root->left = insert_node(data, root->left);
else
root->right = insert_node(data, root->right);
}
creation of binary search tree will take O(logn)
Take inorder traversal of above binary tree to get the sorted sequence in
O(nlog(logn)) also while doing inorder traversal while printing the root
value also check the count and repeat value that many time.
On Fri, Jun 25, 2010 at 5:21 AM, sharad kumar <[email protected]>wrote:
> You are given an unordered sequence of n integers with many duplications,
> such that the number of distinct integers in the sequence is O(log n).
> Design a sorting algorithm and its necessary data structure(s), which can
> sort the sequence using at most O(n log(log n)) time.
>
> Give the detailed design.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
