I have not tested this, but it should get you started:
struct item
{
int val;
int freq;
int index;
};
// Compare function for qsort.
// Returns 1 if a occurs with greater frequency than b
// Returns -1 if b occurs with greater frequency than a
// Otherwise returns 1 if a is encountered before b or -1 if b occurs
first.
int cmp(void *a, void *b)
{
if (((struct item *)a)->freq != ((struct item *)b)->freq)
return (((struct item *)a)->freq > ((struct item *)b)->freq) ?
1 : -1;
else
return (((struct item *)a)->index > ((struct item *)b)->index) ?
1 : -1;
}
sortByFreq(int *a, int n)
{
hashmap<int, item*> valMap;
int i,j,k;
for(i = 0; i < n; ++i)
{
if (valMap.contains(a[i]))
{
// Increment frequency count for existing value
++(valMap[a[i]].freq);
}
else
{
// Add new value
struct item *newVal = new struct item;
newVal->val = a[i];
newVal->freq = 1;
newVal->index = i;
valMap.insert(a[i], newVal);
}
}
// Sort items in map by frequency breaking ties by location in
array
int s = valMap.size();
struct item *table = (struct item *)malloc(s * sizeof(struct item
*));
i = 0;
for(hashmap<int, struct item*>::iterator it = valMap.begin(); it !=
valMap.end(); ++it)
table[i++] = *it;
qsort(table,sizeo(struct item *), s, itemCmp);
// Rebuild array
k = 0;
for(i = 0; i < s; ++i)
{
for(j = 0; j < table[i]->freq; ++j)
a[k++] = table[i]->val;
free(table[i]);
}
free(table);
}
On Apr 16, 12:35 pm, rahul sharma <rahul23111...@gmail.com> wrote:
> Can anyone give me example using hash+linked list method ..although i got
> dave method.but still...
>
>
>
>
>
>
>
> On Tue, Apr 16, 2013 at 8:58 PM, Dave <dave_and_da...@juno.com> wrote:
> > @Varun: Here is an algorithm using sorting only:
>
> > 1. Append an index onto each number, so your example becomes {{4,0},
> > {3,1}, {2,2}, etc.}
>
> > 2. Sort the numbers and their associated indices into ascending order by
> > number. Your example becomes {{2,2}, {2,6}, {3,1}, {4,0}, {4,4}, etc.}. If
> > the sort is not stable, the indices on equal numbers may not be in order,
> > as I've shown here, but that doesn't matter. It will be taken care of in
> > the next step.
>
> > 3. Scan the array, and collapse every sequence of adjacent entries with
> > equal numbers into one entry with the lowest index, and append the
> > frequency to the entry. Your example becomes {{2,2,2}, {3,1,1}, {4,0,2},
> > etc.}
>
> > 4. Sort the array with frequency as the primary key and index as the
> > secondary key. You get {{4,0,2}, {2,2,2}, {6,5,2}, {3,1,1}, {5,1,3}}.
>
> > 5. Reexpand the array by repeating each number according to its frequency,
> > giving {4,4,2,2,6,6,3,5}.
>
> > Dave
>
> > On Wednesday, February 1, 2012 2:58:43 AM UTC-6, Varun wrote:
>
> >> I was asked this question sometime during an interview.
>
> >> WE have an array of known length. The elements in array can be repetitive.
> >> now sort the array based on frequency of occurrence of each element in
> >> array.
> >> Eg: a= {4.3.2.5.4.6.2.6}
> >> after sorting a={4,4,2,2,6,6,3,5}
>
> >> 4,2,6 all occurs twice, in this case retain the order in which they
> >> appeared in original array.
> >> I was able to give a solution using hashing the elements of the array to
> >> a new array, and if hash matches, incrementing the count, and then sort the
> >> hash values. Later, re scan the array to retain the order in case there's a
> >> match in frequency of any two element.
>
> >> Looking for better alternatives.
> >> Please pour in.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visithttps://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
