@aarthi, Its seems like ur worried only about frequency, not the sorting. If its a count sort you're trying to explain,then it requires huge space.. And i guess there is no O(n) sort except count sort, which won't be a gr8 soln. for the original problem
Regards, Vignesh On May 19, 4:09 pm, Aarthi Thangamani <aarthi.thangam...@gmail.com> wrote: > If you are using an extra space to count, why need a heap? An array of size > k can be used to first count the occurances. Then run through the original > array of size N and fill it according to the count our occirances using the > constant k size array. Space O(k) and time O(N) is the best thing I think > of. :( > > On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY < > > > > jaanu.cher...@gmail.com> wrote: > > > Here u r using extra space to store count values.. > > > ---------------------------------------- > > CHERUVU JAANU REDDY > > M.Tech in CSIS > > > On Tue, May 18, 2010 at 7:01 PM, Jagadish M <jagadis...@gmail.com> wrote: > > >> On May 18, 8:29 am, Terence <technic....@gmail.com> wrote: > >> > How do you maintain the heap? Could you explain in detail for the > >> > following example: > >> > 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) > > >> Basically, in each node we maintain the key and its count. > > >> Initially, heap has the first element. > >> 1:1 > > >> Search for 2 and insert( since its not found) > >> 1:1 > >> / > >> 2:1 > > >> Search for 3 and insert ( since its not found). > > >> 1:1 > >> / \ > >> 2:1 3:1 > > >> Search for 3; since 3 is already there increment its count by 1. > > >> 1:1 > >> / \ > >> 2:1 3:2 > > >> Search for 2; since 2 is already there increment its count by 1. > > >> 1:1 > >> / \ > >> 2:2 3:2 > > >> and so on... > > >> Since, there are only k distinct keys the heap size will at most be k; > >> so each search/insert/increment operation takes O(log k) time. > > >> Jagadish > >>http://www.cse.iitb.ac.in/~jagadish > > >> > On 2010-5-17 22:38, Jagadish M wrote: > > >> > > The best algorithm I can think of is to maintain a heap of k elements. > >> > > Takes O(n log k) time. > >> > > Is anything told about the values of the keys? If the keys have values > >> > > less than N, then it is possible to do > >> > > what you say, i.e sort them in place. > > >> > > -Jagadish > >> > >http://www.cse.iitb.ac.in/~jagadish > > >> > > On May 13, 7:06 pm, divya<sweetdivya....@gmail.com> wrote: > > >> > >> This problem was asked in google phone interview. We have N element > >> > >> array with k distinct keys(No relation between k& N given so assume > >> > >> k<N) > >> > >> What is the best method to sort this array without using any extra > >> > >> memory? Please elaborate. > > >> > >> -- > >> > >> 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 athttp:// > >> 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 athttp:// > >> 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. > > > -- > > 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. > For more options, visit this group > athttp://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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
