Mostrar Mensajes
No he revisado si el código está correctamente implementado, ya que es tortuoso y fuerza a uno a desistir, mirando solo por encima. ...dando por supuesto que te funciona bien, ya que tú mismo así lo expresas. de hecho sería adecuado que antes de introducir esas líneas d ecódigo verificaras que el algoritmo ordena correctamente la lista...
...entonces (si el algoritmo funciona bien) lo que te resta es llevar la cuenta en el sitio adecuado.
Y dónde se debe llevar la cuenta?. Allí dónde dicho valor es asignado desde la lista 'right'.
Punto 1: - Dado que el valor 1 es el menor la cuenta debe llevarse solo cuando (y nada más que cuando) el valor 1 se localiza en la lista de la derecha (right, el grupo de índices mayor). Hay 2 sitios donde esto puede suceder. Nota el 'puede suceder', ya que esto implica un condicional, como verás...
Aclarado esto... el pseudocódigo del meollo de la cuestión:
Código:
...
hacer mientras ((i < left.length) y (j < right.length))
Si (left[i] <= right[j])
a2[k] = left[i]
i +=1
sino
// Punto 1:
a2[k] = right[j]
si a2[k] = 1 //valor
cont +=1
fin si
j +=1
fin si
k +=1
siguiente
...
//Punto 2:
hacer mientras (j < right.length) {
a2[k] = right[j]
//si a2[k] = 1 //valor
// cont +=1
//fin si
j +=1
k +=1
siguiente
Al terminar ese bucle, en efecto, al menos una de las listas (left, right) puede no haberse recorrido hasta el final, luego toca pasar el resto de dicha lista a la de a2, en ese caso no hay intercambio de posición.
Punto 2: - Pero si el valor 1 estuviera en ese resto de la lista, no deberá contarse. Técnicamente en este apartado, no debe contarse porque solo trata de regresar fusionar el resto de la lista de la derecha en la lista principal.
No obstante lo he dejado puesto y comentado, por si el problema se considera de otro criterio...
Para terminar, la variable cont, da demasiadas vueltas de acá para allá, es más sencillo si simplemente lo declaras a nivel de la clase, antes de ejecutar el algoritmo se le da el valor 0 y al final se exhibe su cuenta... La razón es que dicha variable modifica el algoritmo, el algoritmo y todas las funciones dependientes, por tanto no son independientes de su uso, luego ni es práctico ni precisa ser aislada en cada función. De hecho si más adelante se reclama modificar el algoritmo para que haga otra cosa distinta, los cambios serán menores.
Es decir, trata de independizar el trabajo del algoritmo, de lo que luego se solicita internamente del algoritmo (llevar una cuenta específica), que incluso uno podría añadir ese código como código de compilación condicional, pero que sin ser necesario es adecuado para reflejar la diferencia entre el código del algoritmo y el código extra para cumplir lo solicitado.
Remarco en rojo (y por ello lo meto en etiqeutas quote y no code), los cambios principales... del resto de funciones comenta también el 'return cont', solo nos interesa hacer la cuenta (si hemos declarado dicha variable a nivel de la clase).
Citar
public class Inversiones {
int cont=0;
int valor=1;
...
private static int ordenar(double[] a2, int min, int max) {
int cont=0;
int middle = (min+max)/2;
if(min<max) {
//cont =
ordenar (a2, min, middle);
//cont = cont +
ordenar (a2, middle + 1, max);
//cont = cont +
merge (a2, min, middle, max);
}
//return cont;
}
...
public static void main(String[] args) throws IOException {
Scanner leer = new Scanner(new File("C:\\Ruta\\InversionsTest.dat"));
int nCases = leer.nextInt();
double a[] = new double[nCases];
for(int i=0; i<nCases; i++) {
a= leer.nextInt();
}
cont = 0;
valor =1;
ordenar(a, 0, a.length-1));
System.out.println("El número de inversiones que tiene el array dado es: " + cont
}
int cont=0;
int valor=1;
...
private static int ordenar(double[] a2, int min, int max) {
int middle = (min+max)/2;
if(min<max) {
//cont =
ordenar (a2, min, middle);
//cont = cont +
ordenar (a2, middle + 1, max);
//cont = cont +
merge (a2, min, middle, max);
}
//return cont;
}
...
public static void main(String[] args) throws IOException {
Scanner leer = new Scanner(new File("C:\\Ruta\\InversionsTest.dat"));
int nCases = leer.nextInt();
double a[] = new double[nCases];
for(int i=0; i<nCases; i++) {
a= leer.nextInt();
}
cont = 0;
valor =1;
ordenar(a, 0, a.length-1));
System.out.println("El número de inversiones que tiene el array dado es: " + cont
}
Otra cosa, para hacelro más útil, es que declares otra variable a nivel de clase, donde su valor se establece a valor solicitado (1 en el caso presente), tras "cont = 0", así si luego te piden que en vez de hacer la cuenta para el valor 1, te lo reclaman para el valor 1000, te basta cambiar una sola línea de código y es fácil saber donde localizarla. Estas líneas las he marcado de color verde y en el pseudocódigo de más arriba, se utiliza comentado.
...por lo demás como no he probado ni mirado el código a fondo, ten cuidado de agotar el espacio de pila, cosa que se puede producir con funciones recursivas si no están adecuadamente acotadas...
p.d.: al final he tenido un tiempito esta noche y he recreado el algoritmo mergesort, el caso es que tomando tu lista de valores, el número de 'inversiones de 1', que me arroja es de 5.
