Método de Ordenación División e Intercambio recursivo en Lenguaje C

/*Funcion Division: Funcionamiento:
Se tiene un vector vec con limites linf (inferior) y lsup (superior). Se necesitan dos
indicadores: uno que señala inicialmente el principio del vector pini <- linf y otro que indica el final pfin <- lsup. Como elemento pivote se utilizará uno escogido aleatoriamente. El índice pini recorre el vector de izquierda a derecha hasta encontrar un elemento que sea mayor que el del pivote. De la misma forma y a partir del final el índice pfin se desplaza hasta encontrar un elemento menor que el del pivote. Si pinipfin. El proceso de partir el vector acabará intercambiando el elemento pivote con el elemento pini, si pini es menor que pivote, o con el elemento pfin si pivote es menor que pfin.*/

void division (int *vec, int linf, int lsup, int *pini, int *pfin, int *ncomp, int *nmov)
{
int pivote, aux;
/*random devuelve un valor aleatorio entre linf y lsup, ambos inclusive */
pivote = linf + rand () % (lsup - linf + 1);
*pini = linf;
*pfin = lsup;
while (*pini <= *pfin)
{
while ((*pini <= lsup) && (*ncomp = *ncomp + 1, vec[*pini] <= vec[pivote]))
*pini = *pini + 1;
while ((*pfin >= linf) && (*ncomp = *ncomp + 1, vec[*pfin] >= vec[pivote]))
*pfin = *pfin - 1;
if (*pini < *pfin)
{
aux = vec[*pini];
vec[*pini] = vec[*pfin];
vec[*pfin] = aux;
*nmov = *nmov + 2; /* Un intercambio son dos movimientos */
*pini = *pini + 1;
*pfin = *pfin - 1;
}
}
if (*pini < pivote)
{
aux = vec[*pini];
vec[*pini] = vec[pivote];
vec[pivote] = aux;
*nmov = *nmov + 2;/* Un intercambio son dos movimientos */
*pini = *pini + 1;
}
else
{
if (*pfin > pivote)
{
aux = vec[pivote];
vec[pivote] = vec[*pfin];
vec[*pfin] = aux;
*nmov = *nmov + 2;/* Un intercambio son dos movimientos */
*pfin = *pfin - 1;
}
}
}
void divinter (int *vec, int linf, int lsup, int *ncomp, int *nmov)
{
/*declaracion de variables*/
int pinicial = 0, pfinal = 0, aux;
if (linf < lsup - 1)
{
/*Llamadas recursivas*/
division (vec, linf, lsup, &pinicial, &pfinal, ncomp, nmov);
divinter (vec, linf, pfinal, ncomp, nmov);
divinter (vec, pinicial, lsup, ncomp, nmov);
}
else
{
if (lsup - linf == 1)
{
if (*ncomp = *ncomp + 1, vec[lsup] < vec[linf]) /* Una comparacion mas */
{
aux = vec[lsup];
vec[lsup] = vec[linf];
vec[linf] = aux;
*nmov = *nmov + 2;/* Un intercambio son dos movimientos */
}
}
}
}
/* Utilizamos este procedimiento como puente */
void metodo1 (int *vec, int n, int *ncomp, int *nmov, float *tiempo)
{
float tiempo1;
tiempo1 = clock ();
*ncomp = 0;*nmov = 0;*tiempo = 0;
divinter (vec, 0, n - 1, ncomp, nmov);
/* El número de pulsos dividido por CLOCKS_PER_SEC da el resultado en
segundos pudiéndose aprovechar los decimales*/
*tiempo = (float) (clock () - tiempo1) / CLOCKS_PER_SEC;
}