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;
}
martes, 20 de octubre de 2009
Implementacion de Merge Sort en Java
Suscribirse a:
Enviar comentarios (Atom)
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...
-
Como programador de aplicaciones Java desde hace más de dos años, puedo decir que la transición al mundo de los API's de Apple, la adopc...
-
Hace tiempo estuve realizando un pequeño compendio para una clase de Diseño de Interfaces Digitales sobre distintos patrones utilizados du...
no logro que me funciones :/
ResponderEliminarHola felipe.
ResponderEliminarEs bueno ver que alguien ha visto esta entrada.
¿Qué error te marca?
Saludos.