How to sort an array by the frequency of appearance of each element?

Question

Not to delay too much I go straight to the point, I am trying to make a program for an exercise that possessed the following instruction:

Build a function int ordenaFreq(int v[], int n) efficient, that is, the running time worst case must be O(n log n), able to sort a vector of elements v of size n by frequency of appearance of each element.

For example, given a vector V = [2, 5, 2, 6, 1, 9999999, 5, 8, 8], its function must return a vector W such that W = [8, 8, 8, 2, 2, 5, 5, 6, 1, 9999999].

I have to use this function in my program but I can’t think of how to solve this problem I’ve used Insertion Sort to organize the vector, but after that I don’t know how to develop this function, mainly taking into account the complexity that has to be used in the function. I currently have the following code made:

#include<stdio.h>

const int max=100;
//Function Prototyping
int InsetionSort(int[],int);
int ordenaFreq(int[],int);
int saida(int);

//Main Function
int main(void)
{
    int escolha=10;
    do
    {
        int v[max];
        int end;

        printf("Entre com o tamanho do arranjo:\n");
        scanf("%d",&end);
        printf("Entre com os elementos do arranjo:\n");
        printf("Numeros com virgula use ponto para separar a parte decimal!\n");
        for(int i=0; i<end; i++)
            scanf("%d",&v[i]);
        InsetionSort(v,end);
        printf("Ordenado fica:\n");
        printf("[");
        for(int i=0; i<end; i++)
            printf("%d ",v[i]);
        printf("]\n");
    }
    while(saida(escolha)!=0);

    return 0;
}
//Auxiliary Functions
int InsetionSort(int v[],int end)
{
    int first,before;
    int aux;

    for(first=1; first<end; first++)
    {
        aux=v[first];
        for(before=first-1;before>=0 && v[before]<aux;before--)
            v[before+1]=v[before];
        v[before+1]=aux;
    }
}
int ordenaFreq(int v[], int end)
{


int saida(int escolha)
{
    printf("Deseja encerrar o programa?\n");
    printf("Digite 0 para fechar ou qualquer outro numero para continuar.\n");
    scanf("%d",&escolha);
    if(escolha==0)
        return 0;
    else return 10;
}

If possible I would also ask you to help me understand the complexity, if it is not too much bother because it is quite recent for me this part so I do not understand very well how it works right.

Answer 1

Well after a lot of trying using the idea of the colleague there, I managed to create a solution that the teacher accepted if someone in the future needs something like this I will leave the code here, I basically used Heapsort to sort the number list and using a matrix I took the frequency of appearance according to the number, then it was just organize it and print on the screen, it was with a different complexity, but the teacher accepted.

//Data:17/09/2018
//Programa:Reorganiza o arranjo de acordo com a frequência de aparição.
#include<stdio.h>
#include<stdbool.h>
const int max=100;
//Prototipação das funções
void ordenaFreq(int*,int);
void heapsort(int,int[]);
int saida(int);
void troca(int*,int*);
//Função Principal
int main(void)
{
    int escolha=10;
    do
    {
        int v[max],end;
        int* aux;

        printf("Entre com o tamanho do arranjo:\n");
        scanf("%d",&end);
        printf("Entre com os elementos do arranjo:\n");
        for(int i=0; i<end; i++)
            scanf("%d",&v[i]);
        printf("Ordenado por tamanho fica:\n");
        heapsort(end,v);
        for(int i=0; i<end; i++)
            printf("%d ",v[i]);
        printf("\n");
        printf("Ordenado por frequencia fica:\n");
        ordenaFreq(v,end);
    }
    while(saida(escolha)!=0);

    return 0;
}
//Funções auxiliares

//Função para organizar o arranjo
void heapsort(int end, int a[]) 
{
   int i = end/2,//Meio do arranjo
       pai,
       filho,
       t;
   while(true) 
   {
      if (i>0)//Se o arranjo não atingiu a posição 0
      {
          i--;//Pega o meio-1 do arranjo
          t=a[i];//Recebe a esquerda
      } 
      else//Se atingiu
      {
          end--;
          if(end==0)//Se atingir a primeira posição do arranjo
              return;
          t=a[end];//Armazena o ultimo elemento
          a[end]=a[0];//Posição final recebe o começo
      }
      pai=i;
      filho=i*2+1;
      while(filho<end) 
      {
          if((filho+1<end)  &&  (a[filho + 1]>a[filho]))
              filho++;
          if (a[filho]>t)//Sube o elemento 
          {
             a[pai]=a[filho];//Troca o progenitor com o descendente
             pai=filho;//Posição do progenitor recebe a do descendente
             filho=pai*2+1;//Pega outro descendente
          } 
          else
             break;
      }
      a[pai]=t;//Recebe o elemento a esquerda
   }
}

//Função para trocar posições 
void troca(int *a, int *b)
{
    int aux;
    aux=*a;
    *a=*b;
    *b=aux;
}

//Função para ordenar de acordo com a frequência
void ordenaFreq(int *v, int end)
{
  int v_aux[2][end];

    //Zerando a matriz
    for(int j=0; j<end; j++)
        for(int i=0; i<2; i++)
            v_aux[i][j]=0;
    //Armazenando a contagem de cada elemento
    for(int j=0; j<end; j++)
    {
        for(int i=0; i<1; i++)
        {
            v_aux[i][j]=v[j];
            for(int k=0; k<end; k++)
            {
                if(v_aux[i][j]==v[k])
                    v_aux[i+1][j]++;
            }
        }
    }
    //Colocando a matriz em ordem decrescente
    for(int k=0; k<end-1; k++)
    {
        for(int j=1; j<end; j++)
        {
            for(int i=1; i<2; i++)
            {
                if(v_aux[i][j-1]<v_aux[i][j])
                {
                    troca(&v_aux[i][j-1],&v_aux[i][j]);
                    troca(&v_aux[i-1][j-1],&v_aux[i-1][j]);
                }
            }
        }
    }
    //Mostrando na tela
    for(int j=0; j<end; j++)
        for(int i=0; i<1; i++)
            if(v_aux[i][j]!=v_aux[i][j+1])//Removendo os repitidos
                for(int k=0; k<v_aux[i+1][j]; k++)
                    printf("%d ", v_aux[i][j]);
    printf("\n");
}

//Função para reiniciar o programa
int saida(int escolha)
{
    printf("Deseja encerrar o programa?\n");
    printf("Digite 0 para fechar ou qualquer outro numero para continuar.\n");
    scanf("%d",&escolha);
    if(escolha==0)
        return 0;
    else return 10;
}