2

Para não delongar demais vou direto ao ponto, estou tentando fazer um programa para um exercício que possuí a seguinte instrução:

Construa uma função int ordenaFreq(int v[], int n) eficiente, isto é, o tempo de execução no pior caso deve ser O(n log n), capaz de ordenar um vetor de elementos v de tamanho n por frequência de aparição de cada elemento.

Por exemplo, dado um vetor V = [2, 5, 2, 6, −1, 9999999, 5, 8, 8, 8], sua função deve retornar um vetor W tal que W = [8, 8, 8, 2, 2, 5, 5, 6, −1, 9999999].

Tenho que usar essa função no meu programa mas não consigo pensar em como resolver esse problema já usei o Insertion Sort para organizar o vetor, mas depois disso não sei como desenvolver essa função, principalmente levando em consideração a complexidade que tem que ser utilizada na função. Atualmente tenho o seguinte código feito:

#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;
}

Se possível gostaria também de pedir que me ajudasse entender a complexidade, se não for muito incomodo porque é bastante recente para mim essa parte então não entendo muito bem como funciona ela direito.

4
  • Eu faria uso da estrutura de dados heap, neste momento não poderei fazer essa solução, mas amanha venho aqui postar a minha resposta. A complexidade podiar ser como por exemplo N + N.log(N) ? A minha ideia era percorrer o vetor todo O(N) e depois de saber quantas vezes ocorre inserir numa heap O(N log(N)) Commented 12/09/2018 às 1:02
  • Sim, n somado ou subtraído não possui muito problema, a professora despreza eles no calculo da complexidade do programa, acho que entendi mais ou menos a ideia que você teve, como a gente está aprendendo ainda tais conteúdos realmente é complexo ver esses caminhos principalmente quando se tem esse limite de complexidade envolvido.
    – Vinícius
    Commented 12/09/2018 às 1:44
  • Posso fazer essa implementação que disse? Como disse N + Nlog(N) fica Nlog(N), porque é desprezado. Se voce quiser que eu faça essa implementação diga algo. Commented 12/09/2018 às 10:02
  • Sim, faça por favor gostaria de ver como ficaria o código que você está pensando.
    – Vinícius
    Commented 12/09/2018 às 14:18

1 Resposta 1

0

Bem depois de muito tentar utilizando a ideia do colega ali, consegui criar uma solução que a professora aceitou caso alguém futuramente precise de algo assim vou deixar o código aqui, basicamente utilizei o Heapsort para ordenar a lista de número e usando uma matriz eu peguei a frequência de aparição de acordo com o número, depois foi só organiza-lo e imprimir na tela, ficou com uma complexidade diferente, mas a professora aceitou.

//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;
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .