Foros aprenderaprogramar.com
Aprender a programar => C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más => Mensaje iniciado por: arcanFAC en 06 de Marzo 2016, 00:54
-
Hola a todos. Queria programar un metodo de ordenamiento en este caso mergeSort. El punto es que lo hize pero probandolo me doy cuenta de que en las mayorias de las situaciones no sirve, es decir sirve cuando nunca se particiona en arreglos de tamaño impar. osea cuando el arreglo a ordenar es de tamaño 2, 4, 8, 16, 32, 64... en caso contrario en algun punto me imprime al inicio varios ceros.... dejo el codigo por si alguien me indica el error....
import java.util.Scanner;
public class TestMerge {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int cantidad = sc.nextInt();
int[] arreglo = new int[cantidad];
for(int i=0; i<cantidad; i++)
arreglo[i] = sc.nextInt();
mergeCall(arreglo);
sc.close();
for(int i:arreglo)
System.out.println(i);
}
static void mergeCall(int[] arreglo){
int size = arreglo.length;
if(size> 1){
if(size % 2 == 0){
int[] izq = new int[size/2];
int[] der = new int[size/2];
depurador(arreglo, izq, 0, size/2);
depurador(arreglo, der, size/2, size);
mergeCall(izq);
mergeCall(der);
mezclador(arreglo, izq, der);
}else {
int[] izq = new int[size/2];
int[] der = new int[(size/2) + 1];
depurador(arreglo, izq, 0, size/2);
depurador(arreglo, der, size/2 + 1, size);
mergeCall(izq);
mergeCall(der);
mezclador(arreglo, izq, der);
}
}
}
static void depurador(int[] arreglo, int[] arreglo2, int inicio, int fin){
int contador = 0;
for(int i=inicio; i<fin; i++){
arreglo2[contador] = arreglo[i];
contador++;
}
}
static void mezclador(int[] arreglo, int[] izq, int[] der){
int contadorIzq = 0;
int contadorDer = 0;
int contadorArr = 0;
while(contadorArr < arreglo.length){
if(contadorIzq >= izq.length){
arreglo[contadorArr] = der[contadorDer];
contadorDer++;
}
else if(contadorDer >= der.length){
arreglo[contadorArr] = izq[contadorIzq];
contadorIzq++;
}
else if(izq[contadorIzq] > der[contadorDer]){
arreglo[contadorArr] = der[contadorDer];
contadorDer++;
}
else{
arreglo[contadorArr] = izq[contadorIzq];
contadorIzq++;
}
contadorArr++;
}
}
}
Gracias de antemano...
-
Hola!
Para quien quiera conocer en qué consiste mergesort, primero se divide una lista de números en sublistas hasta llegar a un tamaño dado (que puede ser listas de 1 elemento: 1 elemento ya es una lista ordenada). Luego se van fusionando las sublistas eligiendo los elementos de menor a mayor para formar sublistas ordenadas, que se vuelven a mezclar hasta llegar a una lista que contiene todos los elemento
(http://howtodoinjava.com/wp-content/uploads/2015/10/Merge_sort_algorithm.png)
(https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)
Es recomendable que crees manualmente una lista de números y le apliques el algoritmo. Vete introduciendo mensajes por pantalla que te indiquen lo que va haciendo el algoritmo para ver dónde falla.
Una cosa que debes tener en cuenta es que for(int i:arreglo) {System.out.println(i);} no debe usarse para mostrar una lista ordenada. El for expandido no garantiza que se recorran los elementos de una colección en orden. Para hacer un recorrido en orden se recomienda usar un for tradicional.
Saludos!