martes, 20 de octubre de 2009

Implementacion de Merge Sort en Java



private int[] mergeSortImpl(int[] array) {
// Caso base. Un arreglo de cero o un elemento ya esta ordenado,
// asi que lo regresamos.
if (array.length <= 1) {
return array;
}
int puntoMedio = array.length / 2;
// Creamos subarreglo izquierdo
int[] izquierdo = new int[puntoMedio];
for (int i = 0; i < puntoMedio; i++) {
izquierdo[i] = array[i];
}
// Creamos el subarreglo derecho
int[] derecho = new int[array.length - puntoMedio];
for (int i = 0; i < array.length - puntoMedio; i++) {
derecho[i] = array[puntoMedio + i];
}
// Ordenamos las dos mitades recursivamente
int[] izquierdoOrdenado = mergeSortImpl(izquierdo);
int[] derechoOrdenado = mergeSortImpl(derecho);
//Mezclamos la solucion---
// El indice i es para recorrer el subarreglo izquierdo
int i = 0;
// El indice j es para recorrer el subarreglo derecho
int j = 0;
// En 'resultado' guardamos el resultado de la mezcla de los dos
// subarreglos
int[] resultado = new int[izquierdoOrdenado.length + derechoOrdenado.length];
/**
* Terminamos de mezclar cuando i + j ya recorrieron todos los elementos
* de los dos subarreglos
*/
while (i + j < izquierdoOrdenado.length + derechoOrdenado.length) {
// a) Si i ya llego al ultimo elemento del subarreglo izquierdo
// copiamos el valor del siguiente elemento del subarreglo
// derecho e incrementamos el indice j para, en el siguiente,
// ciclo copiar el elemento de subarreglo derecho que sigue
if (i == izquierdoOrdenado.length) {
resultado[i + j] = derechoOrdenado[j];
j++;
continue;
}
// Lo mismo que a) pero para el subarreglo derecho
if (j == derechoOrdenado.length) {
resultado[i + j] = izquierdoOrdenado[i];
i++;
continue;
}
int elementoIzquierdo = izquierdoOrdenado[i];
int elementoDerecho = derechoOrdenado[j];
// Comparamos cual de los elementos que siguen es menor y ese
// lo copiamos en resultado
if (elementoIzquierdo <= elementoDerecho) {
resultado[i + j] = elementoIzquierdo;
i++;
} else {
resultado[i + j] = elementoDerecho;
j++;
}
}
return resultado;
}

2 comentarios:

  1. Hola felipe.
    Es bueno ver que alguien ha visto esta entrada.
    ¿Qué error te marca?
    Saludos.

    ResponderEliminar

Eliminar la contraseña de un archivo pdf en línea

¿Conoces la contraseña de un archivo pdf y quieres eliminarla para compartirlo con otras personas? Hace poco estuve probando diferentes h...