@Gene :
sorting given input will give:-
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
consider 2-d array;
4 3 5 2 1 - frequency of corresponding unique data at position arr[1][]
1 2 3 4 5 - unique data
min-heapify arr[0][] - first row and keep track of
the corresponding frequency.
now extract-min and expand it accordingly
for example extract 5 , corresponding frequency found is 1 ,so insert 5 in
array.
or
we can represent each node:-
struct node{
int unique_data;
int frequency;
};
so no need of scanning all values for each extract_min operation.
thats what i was trying to say before.
On Mon, Dec 26, 2011 at 7:49 PM, Gene <[email protected]> wrote:
> 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 <[email protected]> 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 [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.
>
>
--
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.
