Ir ao conteúdo
  • Cadastre-se
rafinha90

Ordenação em tempo linear por contagem

Recommended Posts

Será quem alguem pode me ajudar em 2 coisas?

Gostaria de saber se o código a seguir pode realmente ser considerado como em tempo linear O(n).


bool
sort(int values[], int n)
{
int temp[n], cont[n];
int max;
for (int i = 0; i < n; ++i)
{
cont[i] = 0;
}
for (int i = 0; i < n; ++i)
{
temp[i] = values[i];
}
for (int i = 0; i < n; i++)
{
max = temp[i];
for (int j = 0; j < n; ++j)
{
if (max > temp[j])
{
cont[i]++;
}
}
}
for (int i = 0; i < n; ++i)
{
values[cont[i]] = temp[i];
}
int cont2 = 0, cont3 = 0;
int temp2;
for (int i = 1; i < n; ++i)
{
if (values[i] < values[i - 1])
{
cont2++;
printf("1-)%d\n", values[i]);
}
temp2 = values[i];
for (int j = 0; j < n; ++j)
{
if (temp2 == values[j] && i != j)
{
cont3++;
printf("2-)%d\n", values[j]);
}
}
}
printf("\n\n%d Numeros fora de ordem!\n", cont2);
printf("%d Numeros iguais\n", cont3);


return true;
}

Depois que eu declaro cont2 é só pra fins de verificação do código enquanto implemento, após terminar, essa parte some.

O código ordena perfeitamente os números, contanto que não tenha nenhum numero repetido e essa é a segunda ajuda que queria de vocês: Alguém tem ideia de como fazê-lo funcionar mesmo que existam números repetidos? E lógico, mantê-lo o mais próximo de tempo linear possível.

Edit

-----------------------------------------------------------------------------

Ahh, mais uma coisa, alguem sabe um jeito inicializar array com um valor igual pra todos os espaços, pra substituir aquele primeiro for, sem usar memset().

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×