Sorting array elements based on the frequency of each element

Question

I'm looking for an algorithm in C that sorts array elements by frequency (least to most frequent). For example:

array[10] = {1, 1, 1, 5, 2, 3, 3, 3, 3, 4}; //initial array

array[10] = {5, 4, 2, 1, 1, 1, 3, 3, 3, 3}; //post-sorting array

The order of the elements with similar frequencies (5, 4, and 2 in the example above) do not matter, so long as they are grouped with others of the same frequency.

I am not sure how to go about doing this, I saw THIS , however it is in matlab (which I don't know) rather than C, and it relies heavily on library functions, something I'm trying not to do.

score 2 · Answer 1 · answered Apr 23 '16 at 21:35

You could create a struct that contains the element and the frequency of the element, and you could also avoid duplicates when inserting an element into the array just by increasing the freq field.

For example:

typedef struct elem{
     int value;
     int freq;
} element;

and then sort the array element[N] frequency-wise, maybe with an algorithm like qsort

score 1 · Answer 2 · answered Apr 23 '16 at 21:33

typedef a struct containing value and frequency. Make an array of 10 of them to make a frequency table, and set a table count to 0 initially.

Iterate the source array and assemble the frequency table, incing the count if a value is found that has no table entry yet.

Use qsort to sort the frequency table by ascending frequency.

Iterate the sorted frequency table, building up and output array as you go. You could use the input array as the output array, should you wish.

If you don't want to use the qsort lib function, substitute your own sort.

Sorting array elements based on the frequency of each element

2 Answers2