Thread: print values of array by popularity

Hello everyone.

Given an array with integer values in the range [0, 100], print the values by popularity (number of time it appears in the array).

example:
array: 60, 60, 70, 80, 80, 80, 80, 100;

output: 80 80 80 60 60 70 100.

complexity restriction: should be linear.
cant use advance data structure like lists or hashmaps, only arrays.
structs are not allowed.

my idea:
to build counter array of buckets of size 101, and count each value.
then i need to sort the counter array(its still linear), but how i can keep track that the value of 80 appeared 3 time?
I mean i need to sort the values of the counter with the indexes as well.

Thanks in advance

Use a struct for your counter array elements consisting of two ints: one for the count, one initialized to the original position number.

Code:

struct {
    int count;  // init to zero
    int value;  // init to the original position (0 to 100)
} counts[101];

Sorry, my mistake.
How about "parallel arrays" then?

Code:

int values[101]; // init with 0 to 100
int counts[101] = {0};

Then when you sort counts, move the values elements around with the counts elements.