Su un array ordinato mi viene in mente una soluzione "stravagante"..

Facciamo conto:

codice:
int array[] = { 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5 };
Il primo 1 ha indice 0;
Il primo 2 ha indice 3;
Il primo 3 ha indice 4;
Il primo 4 ha indice 6;
Il primo 5 ha indice 10.

3 - 0 = frequenza di 1;
4 - 3 = frequenza di 2;
6 - 4 = frequenza di 3;
10 - 6 = frequenza di 5.

E` un po` palloso e al momento non ho molta voglia di scrivere codice, quindi vedi un po`. Tanto e` semplicissimo.

Ciao.