You'll have to create a balanced BST. Otherwise, depending on the order of the dataset, it might degenerate into a linked list, which doesn't make searching an O(log n) process.
Dave On Jun 25, 12:07 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%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
