Any reasonable algorithm is goingto compute a histogram of the data then sort into frequency order to produce the output.
The histogram (map from data values to frequency counts) can be stored in a simple array if the data are small integers as in the example. If the data are not nice, then a hash table is a good choice. Run time will be O(n + N log N) where n is the number of input data and N is the number of unique data values. If you have many data but only a few ( O(1 / log n) ) unique values, the run time is linear. If you have O(n) unique values, it's n log n. I think this bound is tight. Note: It does not make much sense to use heaps in this problem (unless you're sorting with heapsort) as some have proposed because you can't use the min or max frequency values until you've scanned all the input. On Dec 24, 12:27 pm, Ankur Garg <ankurga...@gmail.com> wrote: > how can one do frequency sort . > > Suppose we have an integer array like > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 > > Then 1 is appearing 4 times > 2 - 3 > 3- 5 > 4-2 > 5-1 > > Then if we sort by frequency we shud have this as result > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 > > How to do it -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
