Eis o código:
/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 4
*
* Ordenação por distribuição (aka radix sort)
*
**/
#include
#include
#define BASEMAX 10
#define UNDERFLOW -1
#define OVERFLOW -1
typedef struct cel
{
int chave;
struct cel *prox;
} celula;
/* complexidade desta função: O(tamanho da fila) */
void imprimeFila (celula *inicio)
{
celula *varre = inicio;
printf("\n ordenando -> ");
while (varre != NULL)
{
printf (" %d ", varre->chave);
varre = varre->prox;
}
printf("\n\n");
}
/* complexidade desta função: O(1) = constante */
int insereNaFila (int x, celula **inicio, celula **fim)
{
celula *nova;
nova = malloc (sizeof (celula));
if(nova == NULL)
return OVERFLOW;
nova->chave = x;
nova->prox = NULL;
if((*fim) == NULL)
*inicio = nova;
else
(*fim)->prox = nova;
*fim = nova;
return 0;
}
/* O(1) */
int proximoDaFila (int *valorDevolvido, celula **inicio, celula **fim)
{
celula *morta;
if(*inicio == NULL)
return UNDERFLOW;
morta = *inicio;
*valorDevolvido = (*inicio)->chave;
if(morta->prox == NULL)
*fim = NULL;
*inicio = morta->prox;
free (morta);
return 0;
}
/* O(tamanho da fila) */
void removeFila(celula* fila)
{
celula* morta;
while(fila != NULL)
{
morta = fila;
fila = fila->prox;
free(morta);
}
}
/* funções auxiliares */
/* O(1) */
int max(int um, int outro)
{
if(um > outro)
return um;
return outro;
}
/* O(número de dígitos de umNumero) */
int numDigitos(int umNumero)
{
int numDig = 1;
while(umNumero > 0)
{
umNumero /= 10;
numDig++;
}
return numDig;
}
/* O(i) */
int iesimoDigitoMenosSignif(int numero, int i)
{
while(i > 1)
{
numero = numero / 10;
i--;
}
return numero % 10;
}
int main()
{
celula* inicioDaFilaASerOrdenada;
celula* fimDaFilaASerOrdenada;
celula* iniciosDasFilas[BASEMAX];
celula* finaisDasFilas[BASEMAX];
int quantDeNumeros, base, numDig;
int i, j; /* contadores */
int k, temp; /* variáveis auxiliares */
inicioDaFilaASerOrdenada = NULL;
fimDaFilaASerOrdenada = NULL;
printf(" Base numérica? \n -> ");
scanf("%d", &base);
for(i = 0; i < base; i++) /* laço 1, executado 'base' vezes */
{
iniciosDasFilas[i] = NULL; /* O(1) */
finaisDasFilas[i] = NULL; /* O(1) */
}
printf(" Quantidade de números? \n -> ");
scanf("%d", &quantDeNumeros);
printf(" Digite os números a serem ordenados:\n");
/* Agora leremos os números a serem ordenados e, a cada número,
* inserimos esse número na fila principal e contamos seu número
* de dígitos para guardar o maior deles */
numDig = 0;
for(i = 0; i < quantDeNumeros; i++) /* laço 2, executado
'quantDeNumeros' vezes */
{
printf(" --> "); /* O(1) */
scanf("%d", &temp); /* O(1) */
insereNaFila(temp, &inicioDaFilaASerOrdenada, /* O(1) */
&fimDaFilaASerOrdenada);
numDig = max(numDig,
numDigitos(temp)); /* O(número de dígitos de temp) */
}
/* o algoritmo consite basicamente em numDig iterações */
for(i = 1; i <= numDig; i++) /* laço 3, executado 'numDig' vezes */
{
/* primeiro varremos a fila principal e distribuímos
* seus elementos pelas outras filas, de acordo com
* o i-ésimo dígito menos significativo */
for(j = 0; j < quantDeNumeros; j++) /* laço 3.1, executado
'quantDeNumeros' vezes */
{
proximoDaFila(&temp, &inicioDaFilaASerOrdenada,
&fimDaFilaASerOrdenada); /* O(1) */
k = iesimoDigitoMenosSignif(temp, i); /* O(i) */
insereNaFila(temp, &(iniciosDasFilas[k]), /* O(1) */
&(finaisDasFilas[k]));
}
/* agora concatenamos as filas na fila principal */
for(j = 0; j < base; j++) /* laço 3.2, executado 'base' vezes */
{
/* enquanto tem elementos na fila j */
while(proximoDaFila(&temp, &(iniciosDasFilas[j]),
&(finaisDasFilas[j])) != UNDERFLOW)
{ /* laço 3.2.1, executado 'quantDeNumeros' vezes */
insereNaFila(temp, &inicioDaFilaASerOrdenada,
&fimDaFilaASerOrdenada); /* O(1) */
}
}
}
imprimeFila(inicioDaFilaASerOrdenada); /* O(quantNumeros) */
removeFila(inicioDaFilaASerOrdenada); /* O(quantNumeros) */
system("pause");
return 0;
}
/* Análise da complexidade:
*
* Basta somar as complexidades de cada linha. A complexidade de um laço é
* dada pelo somatório (variando o contador do laço), da complexidade do seu
* bloco de comandos, geralmente em função do contador. Mas se a
* complexidade do bloco interno não depender do contador, basta multiplicar
* essa complexidade pelo número de iterações do laço. Assim temos:
*
* complexidade do laço 1 = 2 * 'base' = O(base)
*
* complexidade do laço 2 = (3+num de dígitos de temp) * 'quatDeNumeros' =
* [no pior caso] = 3+numDig * 'quantDeNumeros' =
* = O(numDig*quantDeNumeros)
*
* laço 3 = soma (para i = 0 ... 'numDig') de:
* complexidade do laço 3.1 + complexidade do laço 3.2
* = soma (para i = 0 ... 'numDig' de:
* 2+i + 1*'base'
* = O(2)*'numDig' +
* (soma (para i = 0 ... 'numDig' de: i) +
* O(base)*'numDig'
* = O(numDig) + O(numDig) + O(base*numDig)
* = O(base*numDig)
*
* complexidade do programa inteiro (função main):
* uma porção de operações de tempo constante (declaração e inicialização
* de variáveis) + soma das complexidades dos laços + complexidade das duas
* últimas linhas =
*
* = O(1) + O(base) + O(numDig*quantDeNumeros) +
* O(base*numDig) + 2*O(quantDeNumeros) =
*
* = O(numDig*(quantDeNumeros + base))
*
* Como utilizamos o tipo int, podemos considerar que a base será no
* máximo 10 (pois uma base maior que essa exigiria o uso de caracteres) e
* que o número de dígitos não ultrapassará 64 na maioria dos casos.
* Com essas considerações, o número de números tem potencial para ser bem
* maior que o tamanho da base e que o número de dígitos.
* Assim, a complexidade fica O(64*quantDeNumeros + 640) = O(quantDeNumeros).
* Logo, este algoritmo é linear no número de números a serem ordenados
*
**/
Nenhum comentário:
Postar um comentário