Bueno, como parte de una tarea de análisis y diseño de algoritmos, tuve que implementar el método mergesort para el ordenamiento de vectores de enteros. Como saben este algoritmo consiste en dividir el arreglo original en arreglos más pequeños, de hecho hasta arreglos de un solo elemento, una vez separados los arreglos, se ordenan a partir de la mezcla de todos ellos. Una vez terminada mi implementación en C de este curiosos método de ordenamiento, les comparto cómo quedo, espero que les sirva, saludos desde México !
PD ya saben cualquier duda de la implementación, estoy a sus ordenes en p.camarillor@gmail.com o en @p_camarillor o en www.facebook.com/p.camarillor
PD ya saben cualquier duda de la implementación, estoy a sus ordenes en p.camarillor@gmail.com o en @p_camarillor o en www.facebook.com/p.camarillor
int * Mergesort(int *v, int longitud)
{
int mitad = longitud / 2;
int residuo = longitud % 2;
int *vectorIzquierdo, *vectorDerecho;
int i = 0;
//Caso base, la lista es de un elemento y se considera ordenado
if(longitud == 1)
{
return v;
}
vectorIzquierdo = (int *)malloc((mitad)*sizeof(int));
vectorDerecho = (int *)malloc((mitad + residuo)*sizeof(int));
//Para cada entero en el vector v antes de la mitad, se agrega a la izquierda
for(i = 0; i < mitad; i++)
{
*(vectorIzquierdo + i) = v[i];
}
//Para cada entero en el vector v despues de la mitad, se agrega a la derecha
int j = 0;
for(i = mitad; i < longitud; i++)
{
*(vectorDerecho + j) = v[i];
j++;
}
//Se llama recursivamente hasta obtener un vector de un elemento
vectorIzquierdo = Mergesort(vectorIzquierdo, mitad);
vectorDerecho = Mergesort(vectorDerecho, (mitad + residuo));
return merge(vectorIzquierdo, mitad, vectorDerecho, (mitad + residuo));
}
int * merge(int *vI, int longitudVectorIzquierdo, int * vD, int longitudVectorDerecho)
{
int *lstResultado;
int cabezaLista = 0;
lstResultado = (int *)malloc((longitudVectorIzquierdo + longitudVectorDerecho)*sizeof(int));
while(longitudVectorIzquierdo > 0 || longitudVectorDerecho > 0)
{
if(longitudVectorIzquierdo > 0 && longitudVectorDerecho > 0)
{
if(*(vI + 0) <= *(vD + 0))
{
*(lstResultado + cabezaLista) = *(vI + 0);
//Se elimina el elemento que se ha ingresado en la lista final
vI++; //Se incrementa la posición del apuntador
longitudVectorIzquierdo--;//Se resta el número de elementos
cabezaLista++;
}
else
{
*(lstResultado + cabezaLista) = *(vD + 0);
//Se elimina el elemento que se ha ingresado en la lista final
vD++;
longitudVectorDerecho--;
cabezaLista++;
}
}
else if(longitudVectorIzquierdo > 0)
{
*(lstResultado + cabezaLista) = *(vI + 0);
//Se elimina el elemento que se ha ingresado en la lista final
vI++;
longitudVectorIzquierdo--;
cabezaLista++;
}
else if(longitudVectorDerecho > 0)
{
*(lstResultado + cabezaLista) = *(vD + 0);
//Se elimina el elemento que se ha ingresado en la lista final
vD++;
longitudVectorDerecho--;
cabezaLista++;
}
}
return lstResultado;
}
