/*METODO DE ORDENACION SELECCION CUADRATICA: FUNCIONAMIENTO:
La lista de entrada, con n elementos, se divide en raíz cuadrada de n sublistas, cada una con raíz de n elementos, si n no es cuadrado perfecto las sublistas no cubren todos los elemento teniendo que incrementar en uno el número de elementos e incluso el número de particiones. Cada sublista es objeto de una selección lineal, donde se busca el elemento más pequeño. Estos elementos se transfieren a una lista auxiliar, y en su lugar en la lista de entrada, se coloca el número máximo posible. Cada elemento de la lista auxiliar esta asociado a una sublista. En la lista auxiliar se realiza a continuación otra selección lineal en busca del elemento más pequeño, que se transferirá a la lista de salida, siendo ocupada su posición por el siguiente elemento más pequeño de la sublista a la cual pertenece. El proceso continua hasta que se haya llenado la lista de salida. */
void selpart (int vec[], int n, int aux[], int nele, int part, int *ncomp, int *nmov)
{
/*Declaracion de variables*/
int primero, ultimo, elem, pos, menor;
primero = (part - 1) * nele;
if (nele * part < n)
ultimo = nele * part - 1;
else
ultimo = n - 1;
pos = primero;
menor = vec[primero];
for (elem = primero + 1; elem <= ultimo; elem++)
{
if ((*ncomp)++, vec[elem] < menor)/*hacemos una comparacion mas*/
{
menor = vec[elem];
pos = elem;
}
}
aux[part - 1] = menor;
/*hacemos un movimiento mas*/
(*nmov)++;
vec[pos] = INT_MAX;
}
void metodo2 (int vec[], int n, int *ncomp, int *nmov, float *tiempo)
{
/*declaracion de variables*/
int *aux, nelement, npart, m, part, menor, *vecs, e;
aux = (int *) malloc (((int)(sqrt(n)+1))*sizeof(int));
vecs = (int *) malloc (n*sizeof(int));
*tiempo = (float) clock ();
(*ncomp) = (*nmov) = 0;
/*El numero de parte y el numero de elementos es la raiz cuadrada del tamaño del ejemplar*/
nelement = npart = sqrt (n);
/*miramos si n es un cuadrado perfecto*/
if (nelement * npart < n)
{
/*sino lo es, no cubre todos los elementos, y por eso incrementamos en 1 el numero de elementos*/
nelement = nelement + 1;
if (npart * nelement < n)
{
/*como no es cuadrado perfecto habra una parte mas*/
npart = npart + 1;
}
}
/*recorremos todas las partes y llamamos a selpart*/
for (part = 1; part <= npart; part++)
selpart (vec, n, aux, nelement, part, ncomp, nmov);
/*y buscamos el menor de cada parte y lo colocamos en aux*/
for (m = 0; m <= n - 1; m++)
{
menor = aux[0];
part = 1;
/*buscamos el menor de aux y lo colocamos en el vector final, vecs*/
for (e = 1; e <= npart; e++)
{
if ((*ncomp)++, aux[e - 1] < menor)/*hacemos una comparacion mas*/
{
menor = aux[e - 1];
part = e;
}
}
vecs[m] = menor;
(*nmov)++;/*hacemos un movimiento mas*/
selpart (vec, n, aux, nelement, part, ncomp, nmov);
}
for (m = 0; m < n; m++)
{
vec[m] = vecs[m];
}
/* El número de pulsos dividido por CLOCKS_PER_SEC da el resultado en
segundos pudiéndose aprovechar los decimales*/
*tiempo = (((float) clock ()) - *tiempo) / CLOCKS_PER_SEC;
/*Liberamos el vector intermedio y el vector final*/
free(aux);
free(vecs);
}
Entradas
