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 <anandut2...@gmail.com> 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 <sharad20073...@gmail.com>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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.