Sort an array by increasing the frequency of an element

Question

I would like to sort the array, increasing the frequency order. For example, if I had an array

int arr[] = { 3, 3, 10, 2, 5, 10, 10, 2, 2, 2 }; 

or another array will have the following sequence:

 int arr[] = {5, 3, 3, 10, 10, 10, 2, 2, 2, 2}; 

However, I cannot use hashing or maps - I can only use arrays. What I was thinking about is sorting the array using the quick sort algorithm, scanning the sorted array and doing the count in 2d array, so for each element there is an account associated with it, and then sort by count. If the two counts match, then I would just print out the one who first had a lower value. I am having trouble completing the last two steps. I'm not sure how to “match” the score to the index in the 2d array, and I'm not sure how to sort the 2d array by count. Can anyone help me out? Thanks!

Answer 1

How would I encode it without STL (requires additional O (n) memory):

 // Represents a bunch of equal numbers in an array struct Bunch { int x; // value of numbers int n; // count of numbers }; int cmp_int(const void *x, const void *y) { return *static_cast<const int*>(x) - *static_cast<const int*>(y); } int cmp_bunch(const void *x, const void *y) { const Bunch* bx = static_cast<const Bunch*>(x); const Bunch* by = static_cast<const Bunch*>(y); return (bx->n != by->n) ? bx->n - by->n : bx->x - by->x; } void sort_by_freq(int arr[], int arr_size) { // Buffer array to store counted bunches of numbers Bunch* buf = new Bunch [arr_size]; int buf_size = 0; // Sort input array qsort(arr, arr_size, sizeof(int), cmp_int); // Compute bunches Bunch bunch; bunch.x = arr[0]; bunch.n = 1; for (int i = 1; i < arr_size; ++i) { if (arr[i] > bunch.x) { buf[buf_size++] = bunch; bunch.x = arr[i]; bunch.n = 1; } else { ++bunch.n; } } buf[buf_size++] = bunch; // Don't forget the last one! // Sort bunches qsort(buf, buf_size, sizeof(Bunch), cmp_bunch); // Populate bunches to the input array int i = 0; for (int k = 0; k < buf_size; ++k) for (int j = 0; j < buf[k].n; ++j) arr[i++] = buf[k].x; // Don't forget to deallocate buffer, since we cannot rely on std::vector... delete [] buf; } 

Answer 2

Scan your array (sort first but not necessary) and create an array of structure below. Now sort the array of these structures, and then restore the original array.

 struct ElemCount { int Elem; int count; bool operator<(const ElemCount& other) { if (count!=other.count) return count<other.count; return Elem<other.Elem; } };