you will have to call insert functuon for every integer
for 1 to n
insert(int n , node *root)
wouldn't that be n*logn
correct me if i'm wrong......!!!
On Fri, Jun 25, 2010 at 10:37 PM, Anand <[email protected]> wrote:
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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.
