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.
heap
, neste momento não poderei fazer essa solução, mas amanha venho aqui postar a minha resposta. A complexidade podiar ser como por exemploN + N.log(N)
? A minha ideia era percorrer o vetor todoO(N)
e depois de saber quantas vezes ocorre inserir numaheap
O(N log(N))