Ejercicio 2 - Práctico 7

Ejercicio 2 - Práctico 7

de Marco Liguori Hernandez -
Número de respuestas: 3

Buenas,

Estoy teniendo dificultad para entender la solución provista por el libro para este ejercicio.

unknown.png

Comprendo lo que está haciendo con los counters y los Ifs, pero no comprendo como ordena la lista resultante L de Mergear b1,....,bk y bk+1,...,bn. Porque si vas armando la listas según que counter se mueve, no te queda ordenada de mayor a menor, lo cuál puede causar que el segundo If cuente erroneamente las inversiones a la derecha de bi. Por otro lado, no sabría como sería si la lista la voy ordenando de menor a mayor, como acoplo eso con los counters que se mueven en la solución.

Desde ya muchas gracias,

Marco.

En respuesta a Marco Liguori Hernandez

Re: Ejercicio 2 - Práctico 7

de Fernando Fernandez -
Hola.
Opino sobre lo que estás mostrando, que me parece que es correcto. De todos modos, no sé que tan solución 'oficial' del libro puede ser. También parece que falta algo más arriba en donde supongo que se definen que son los a'_1, \cdots, a'_{k} y a'_{k+1,} \cdots, a'_n del segundo y tercer punto (o sea, ¿por qué no son a_1, \cdots, a_{k} y a_{k+1,} \cdots, a_n?).

El algoritmo hace dos recorridas independientes de los datos mediante subalgoritmos en los puntos cuarto y quinto. Ambas son en tiempo lineal.

En el punto cuarto calcula N_3. Los cursores no modifican los datos ni los cambian de posición. Ese algoritmo es el que se ve en las últimas líneas de la publicación.

En el quinto punto es donde se hace la mezcla reordenando los elementos originales. Lo hace mediante el algoritmo MERGE, que no describe porque asume conocido.

Saludos,