domingo, 20 de enero de 2008

Método de Ordenación Por Dígitos en Lenguaje C

/*La función NDigitos devuelve el número de dígitos mayor de los elementos del vector que se le pasa v, de tamaño n.
El mecanismo que se utiliza es sucesivas divisiones entre 10 de cada uno de los elementos del vector para obtener el número de dígitos*/
int NDigitos(int *v, int n)
{
int Contador, Maximo, i;
float Dato;
Maximo=0; /*Se inicializa el número de digitos máximo a 0*/
for (i=0;i {
Dato = (float)(fabs(v[i])); /*Se obtiene su valor absoluto*/
if ((Dato==0)||(Dato==1)) /*En caso de que sea el valor 0 o 1 el número de digitos será 1*/
Contador=1;
Contador=0; /*Se inicializa el numero de digitos del valor a 0*/
while (Dato>1) /*Mientras que el valor sea mayor que 1*/
{
Dato = Dato / 10; /*se va dividiendo entre 10*/
Contador = Contador + 1; /*y se incrementa el número de digitos del valor en 1*/
}
if (Contador>Maximo) /*Si el número de dígitos del valor es mayor que el máximo acumulado, éste pasa a ser el máximo*/
Maximo = Contador;
}
return Maximo; /*Se devuelve el número de dígitos mayor de los elementos del vector*/
}


/*Implementación del metodo1 (Ordenación por Dígitos)*/
/*La ordenación por dígitos consiste en realizar susecivas ordenaciones (dispersión), con respecto
a los dígitos que componen los elementos del vector de entrada, desde el menos al más significativo*/

void Metodo1(int vec[], int n, int *ncomp, int *nmov, float *tiempo)
{
int varaux, varaux1,nd,cadadigito,i,key,digito,*vecs,*cont,cadaelemento,colocador, taux, taux2;
taux=clock();
*ncomp=0;
*nmov=0;
vecs = (int*)malloc(n*sizeof(int)); /*Se necesita crear un vector auxiliar del mismo tamaño que el vector dado*/
if (vecs != NULL)
{
cont = (int*)malloc(11*sizeof(int)); /*También se necesita otro vector auxiliar de 11 elementos*/
if (cont != NULL)
{
nd = NDigitos(vec,n); /*Se calcula el número de dígitos mayor de los elementos del vector*/
varaux = 1;
varaux1 = 10;
for(cadadigito=0;cadadigito {
for(i=1;i<11;i++)
{
cont[i]=0;
}
for (cadaelemento=0;cadaelemento {
key = vec[cadaelemento];
digito = (key%varaux1)/varaux;
cont[digito+1] = cont[digito+1] + 1;
}
cont[0]=1;
for(i=1;i<10;i++)
{
cont[i] = cont[i] + cont[i-1];
}
for (cadaelemento=0;cadaelemento {
key = vec[cadaelemento];
digito = (key%varaux1)/varaux;
colocador = cont[digito];
vecs[colocador-1] = key;
*nmov=*nmov+1;
cont[digito] = cont[digito]+1;
}
for(i=0;i {
vec[i]=vecs[i];
*nmov=*nmov+1;
}
varaux = varaux1;
varaux1 = varaux1 * 10;
}
}
}
free(cont); /*Se libera la memoria requerida*/
free(vecs); /*Se libera la memoria requerida*/
taux2=clock();
*tiempo=((float)(taux2-taux))/CLOCKS_PER_SEC; /*Cálculo del tiempo de ejecución del metodo de ordenación*/
}