Ejercicio resuelto: contar inversiones con mergesort en Java

Ejercicio de examen resuelto en Java: contar parejas desordenadas de un vector en O(n log n) modificando mergesort, con pistas, trazas y errores típicos.

Código de Examen Java Algoritmia Nivel examen Código probado

Algoritmos y Estructuras de Datos · Examen finalEjercicio 4 · 2,5 puntos · 30 min

Una empresa de logística tiene una cinta transportadora por la que deberían pasar los paquetes en orden de peso no decreciente. Un sensor registra el peso de cada paquete, en el orden real en que pasa por la cinta. Para medir cuánto de desordenada ha llegado una tanda, el responsable de calidad define una pareja desordenada como un par de posiciones i < j tales que a[i] > a[j], es decir, un paquete más pesado que pasa antes que otro más ligero.

Dos paquetes con el mismo peso no forman una pareja desordenada, porque el orden no decreciente los admite en cualquier posición relativa. Los pesos son enteros que pueden ser negativos (el sensor registra desviaciones respecto a un peso nominal) y pueden repetirse.

Escribe un programa en Java que lea la tanda por la entrada estándar y escriba el número total de parejas desordenadas. La solución cuadrática que compara todas las parejas no se puntuará en el apartado principal: se exige un algoritmo de coste O(n log n) basado en divide y vencerás.

Formato de entrada. La primera línea contiene un entero n, con 0 ≤ n ≤ 200000. A continuación aparecen n enteros separados por espacios o saltos de línea, cada uno con valor absoluto como máximo 10^9. Si n vale 0, no aparece ningún valor más.

Formato de salida. Una única línea con el número de parejas desordenadas, escrito en decimal y seguido de un salto de línea. Si no hay ninguna pareja, se escribe 0. Ten en cuenta el tamaño máximo que puede alcanzar el resultado con los límites dados.

Abajo tienes un ejemplo de entrada con seis paquetes y la salida que debe producir. Antes de programar, cuenta a mano las parejas del ejemplo para asegurarte de que entiendes la definición, en especial qué ocurre con los dos paquetes de igual peso.

Entrada de ejemplo

6
3 1 4 1 5 2

Salida esperada

6

Lectura correcta de la entrada y tratamiento de los casos límite (n = 0, n = 1, valores negativos y repetidos)

0,5

Mergesort modificado que cuenta las parejas cruzadas en la mezcla con el incremento correcto (mid - i) y la comparación correcta ante empates

1,25

Uso de un tipo entero de 64 bits para el contador, justificando por qué int no basta

0,5

Análisis de complejidad temporal y espacial razonado

0,25

Pistas

Pista 1 · ¿Qué parejas puedes contar sin mirarlas una a una?

Divide el vector en dos mitades. Toda pareja desordenada está entera en la mitad izquierda, entera en la mitad derecha o es cruzada: un elemento en la izquierda y otro en la derecha. Las dos primeras se cuentan recursivamente. El problema es contar las cruzadas en tiempo lineal.

Pista 2 · ¿Qué ganas si las dos mitades ya están ordenadas?

Para contar las parejas cruzadas da igual el orden interno de cada mitad, porque cualquier elemento de la izquierda sigue estando antes que cualquiera de la derecha. Si ambas mitades están ordenadas, al mezclarlas como en mergesort, cuando el elemento de la derecha es estrictamente menor que el de la izquierda, también lo es frente a todos los que quedan por mezclar en la izquierda.

Pista 3 · ¿Cuánto sumas exactamente y qué haces con los empates?

Si la mezcla usa un índice i en la mitad izquierda [lo, mid) y toma un elemento de la derecha porque es menor, quedan mid - i elementos de la izquierda mayores que él. Ante un empate debes tomar primero el de la izquierda; si no, contarás como desordenados paquetes de igual peso.

Solución

Solución explicada

La idea es aprovechar mergesort: ordenar el vector y, de paso, contar las parejas desordenadas. Cada pareja cruzada se descubre justo cuando, durante la mezcla, un elemento de la mitad derecha adelanta a los que quedan en la mitad izquierda. El programa lee los datos con StreamTokenizer, que es rápido y admite números negativos, y delega todo el trabajo en un método recursivo contar.

Se trabaja con intervalos semiabiertos [lo, hi), lo que simplifica las cuentas de longitudes y evita los típicos errores de una posición. Se reserva un único vector auxiliar aux para todas las mezclas.

import java.io.*;

public class Main {

    // Ordena a[lo, hi) y devuelve el numero de parejas desordenadas de ese tramo.
    static long contar(int[] a, int[] aux, int lo, int hi) {
        if (hi - lo <= 1) {
            return 0;
        }
        int mid = (lo + hi) >>> 1;
        long inv = contar(a, aux, lo, mid) + contar(a, aux, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) {
                aux[k++] = a[i++];
            } else {
                inv += mid - i;
                aux[k++] = a[j++];
            }
        }
        while (i < mid) {
            aux[k++] = a[i++];
        }
        while (j < hi) {
            aux[k++] = a[j++];
        }
        System.arraycopy(aux, lo, a, lo, hi - lo);
        return inv;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(
                new BufferedReader(new InputStreamReader(System.in)));
        int n = 0;
        if (st.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) st.nval;
        }
        int[] a = new int[n];
        for (int idx = 0; idx < n; idx++) {
            st.nextToken();
            a[idx] = (int) st.nval;
        }
        System.out.println(contar(a, new int[n], 0, n));
    }
}

El método contar(a, aux, lo, hi) tiene un contrato doble: al volver, el tramo a[lo, hi) queda ordenado y el valor devuelto es el número de parejas desordenadas que había en ese tramo antes de ordenarlo. El caso base es un tramo de cero o un elemento, que no contiene parejas: devuelve 0. Así se cubren directamente los tests de un solo paquete y de tanda vacía.

En el caso recursivo se calcula mid con (lo + hi) >>> 1, que no desborda aunque la suma supere el rango de int. Las dos llamadas recursivas devuelven las parejas internas de cada mitad y dejan ambas mitades ordenadas. Esto es legítimo porque reordenar el interior de una mitad no altera qué parejas son cruzadas: cualquier elemento de la izquierda sigue estando antes que cualquier elemento de la derecha en el vector original.

La mezcla recorre la izquierda con i y la derecha con j. Si a[i] <= a[j], el elemento izquierdo pasa a aux sin sumar nada. En caso contrario, a[j] es estrictamente menor que a[i] y, como la izquierda está ordenada, también menor que a[i+1], …, a[mid-1]. Por eso se suman de golpe mid - i parejas. Cada pareja cruzada se cuenta exactamente una vez: cuando su elemento derecho sale hacia aux.

La comparación con <= es la que hace cumplir la regla del enunciado sobre pesos iguales. En el test Repetidos en orden decreciente, con pesos 7 7 3 3 1, los dos sietes no se cuentan entre sí, ni los dos treses, y el resultado es 8: cada siete forma pareja con 3, 3 y 1 (seis en total) y cada tres con el 1 (dos más). Con < se contarían también los dos empates y saldría 10.

En el ejemplo del enunciado, con 3 1 4 1 5 2, la mitad izquierda [3, 1, 4] aporta 1 pareja (el 3 con el 1) y la derecha [1, 5, 2] aporta otra (el 5 con el 2). Al mezclar [1, 3, 4] con [1, 2, 5], el primer 1 izquierdo sale primero por el empate; después el 1 derecho adelanta a 3 y 4 (suma 2) y el 2 adelanta a esos mismos dos (suma 2). Total: 1 + 1 + 4 = 6.

Los bucles finales copian lo que sobre de cada mitad; el sobrante de la izquierda no suma nada porque esas parejas ya se contaron al salir los elementos derechos. Por último, System.arraycopy devuelve el tramo ordenado a a. En main, si la entrada está vacía, n se queda en 0, y el test Valores negativos confirma que el lector maneja signos: con -1 -5 0 -5 el resultado es 3.

Código y tests en GitLab

Traza paso a paso · generada ejecutando el código

Paso	lo	mid	hi	i	j	inv
1	1	2	3	1	2	0
2	1	2	3	2	3	0
3	0	1	3	0	1	0
4	0	1	3	0	2	1
5	0	1	3	1	3	1
6	4	5	6	4	5	0
7	4	5	6	5	6	1
8	3	4	6	3	4	1
9	3	4	6	4	6	1
10	0	3	6	0	3	2
11	0	3	6	1	3	2
12	0	3	6	1	4	4
13	0	3	6	1	5	6
14	0	3	6	2	5	6
15	0	3	6	3	6	6

Casos de prueba

Caso	Entrada	Salida esperada	Salida real	Resultado
Ejemplo del enunciado	6 3 1 4 1 5 2	6	6	OK
Tanda ya ordenada	5 1 2 3 4 5	0	0	OK
Repetidos en orden decreciente	5 7 7 3 3 1	8	8	OK
Valores negativos	4 -1 -5 0 -5	3	3	OK
Un solo paquete	1 42	0	0	OK
Tanda vacía	0	0	0	OK

Salidas reales: código compilado con Java 21.0.12.1 (Temurin) y ejecutado en un contenedor aislado el 18 de octubre de 2026.

Complejidad

Tiempo. El coste cumple la recurrencia T(n) = 2T(n/2) + Θ(n): dos llamadas sobre la mitad y una mezcla lineal en la que cada comparación hace trabajo constante, incluido el incremento inv += mid - i. Por el teorema maestro, T(n) = Θ(n log n). Con n = 200000 son unos 3,6 millones de operaciones elementales, muy lejos del límite. La versión cuadrática haría unos 2·10^10 comparaciones, inaceptable.

Memoria. Además del vector de entrada se usa un único auxiliar aux de tamaño n, reservado una sola vez en main, más la pila de recursión, de profundidad ⌈log₂ n⌉ (unos 18 marcos para el máximo). En total, Θ(n) de memoria extra. Reservar un vector nuevo en cada llamada no cambia el orden asintótico, pero multiplica las reservas y el trabajo del recolector de basura.

Errores típicos

• Declarar el contador como int: con 200000 pesos en orden estrictamente decreciente hay 199999·200000/2 ≈ 2·10^10 parejas, que desborda int sin error visible y produce un número sin sentido.
• Usar a[i] < a[j] en la mezcla: ante un empate se toma primero el elemento derecho y se cuentan como desordenados paquetes de igual peso.
• Sumar 1 en lugar de mid - i cuando sale un elemento de la derecha, con lo que solo se cuenta una de las parejas que ese elemento forma con lo que queda en la izquierda.
• Sumar también algo en los bucles que vacían el sobrante de la izquierda, contando dos veces parejas que ya se registraron.
• Olvidar copiar aux de vuelta a a: las mitades no quedan ordenadas en el nivel superior y los conteos de las mezclas siguientes son incorrectos.
• No contemplar la entrada con n = 0 o calcular mid como (lo + hi) / 2 con intervalos cerrados mal ajustados, lo que provoca recursión infinita en tramos de dos elementos.

Variantes

Versión de referencia por fuerza bruta

Es la solución que muchos escriben primero y la que conviene usar para comprobar la buena: dos bucles anidados que cuentan cada pareja i < j con a[i] > a[j]. Cuesta Θ(n²), así que solo sirve para tandas pequeñas, pero produce exactamente la misma salida en todos los tests y es útil para validar la versión con mergesort.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(
                new BufferedReader(new InputStreamReader(System.in)));
        int n = 0;
        if (st.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) st.nval;
        }
        int[] a = new int[n];
        for (int idx = 0; idx < n; idx++) {
            st.nextToken();
            a[idx] = (int) st.nval;
        }
        long c = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) {
                    c++;
                }
            }
        }
        System.out.println(c);
    }
}

Contar con un árbol de Fenwick

Otra forma de llegar a O(n log n): se comprimen los pesos a rangos 1..m (ordenando una copia y eliminando duplicados) y se recorre el vector de derecha a izquierda. Para cada a[i] se consulta en un árbol de Fenwick cuántos pesos ya vistos son estrictamente menores (prefijo hasta rango - 1) y después se inserta su rango. Usa la misma memoria y no modifica el vector original.

Lo que preguntará el profesor

«Si sé que el resultado nunca puede ser negativo, ¿por qué no basta con un int? ¿Y cuál es la entrada que produce el valor máximo?»

El máximo se alcanza con los n pesos en orden estrictamente decreciente: todas las parejas están desordenadas y hay n(n-1)/2. Para n = 200000 eso son 19999900000 parejas, casi diez veces el máximo de un int (2147483647). La suma desbordaría en silencio y daría un valor erróneo, posiblemente negativo. Un long llega hasta unos 9,2·10^18, así que basta. El signo no tiene nada que ver: el problema es el rango.

En los temarios

Mergesort y los algoritmos de ordenamiento ocupan un bloque propio en el temario de ISIS1206 Estructuras de datos de la Universidad de los Andes, y la recursividad y el paso entre versiones recursivas e iterativas forman la unidad 2 del programa de Algoritmos y Programación II (75.41) de la Universidad de Buenos Aires. Este ejercicio combina ambos contenidos: un mergesort recursivo al que se le añade un contador.

En Chile, el programa de Diseño y Análisis de Algoritmos de la Universidad de Chile incluye mergesort y cotas inferiores para la ordenación, y el de IIC2133 de la Pontificia Universidad Católica de Chile recoge el diseño y la comparación de estructuras de datos fundamentales, terreno en el que encaja la variante con árbol de Fenwick.

Opinión · El contexto que falta

Lo que más me interesa de este ejercicio no es mergesort, sino el long. En producción, un contador que desborda en silencio es exactamente el tipo de fallo que pasa todas las pruebas pequeñas y revienta con datos reales. El enunciado obliga a mirar los límites antes de escribir una línea.

La otra lección es de método: la versión cuadrática no es un error, es la herramienta para verificar la rápida. Quien entrega solo la optimizada sin nada con qué contrastarla está confiando en la suerte.

Artículos relacionados de LaRebelión

Ejercicio resuelto: pila con vector y paréntesis equilibrados en CEjercicio resuelto: traspuesta, diagonales y sumas de matrices en Python

• Ejercicio resuelto: reparto de trabajo entre hilos en Java
• Ejercicio resuelto: serialización con transient en Java
• Ejercicio resuelto: interfaces, default y múltiples implementaciones en Java

Artículo generado mediante AI.larebelion

Kernel · Dirección de tecnología · España

«El fallo caro aquí no está en la recursión, está en un contador int que nadie dimensionó con el caso peor.»