Cómo fusionar dos matrices ordenadas en Java

1. Introducción

En este tutorial, aprenderemos cómo fusionar dos matrices ordenadas en una sola matriz ordenada.

2. Problema

Entendamos el problema. Tenemos dos matrices ordenadas y nos gustaría fusionarlas en una.

3. Algoritmo

Cuando analizamos el problema, es bastante fácil observar que podemos resolver este problema utilizando la operación de combinación de Merge Sort.

Digamos que tenemos dos matrices ordenadas foo y bar de longitud fooLength y barLength , respectivamente. A continuación, podemos declarar otra matriz fusionada de tamaño fooLength + barLength .

Luego deberíamos atravesar ambas matrices en el mismo ciclo. Mantendremos un valor de índice actual para cada, fooPosition y barPosition . En una iteración dada de nuestro ciclo, tomamos cualquier matriz que tenga el elemento de menor valor en su índice y avanzamos ese índice. Este elemento ocupará la siguiente posición en la matriz fusionada .

Finalmente, una vez que hayamos transferido todos los elementos de una matriz, copiaremos el resto de la otra en la matriz fusionada .

Ahora veamos el proceso en imágenes para comprender mejor el algoritmo.

Paso 1:

Comenzamos comparando los elementos en ambas matrices y elegimos el más pequeño.

Luego incrementamos la posición en la primera matriz.

Paso 2:

Aquí incrementamos la posición en la segunda matriz y pasamos al siguiente elemento que es 8.

Paso 3:

Al final de esta iteración, hemos atravesado todos los elementos de la primera matriz.

Etapa 4:

En este paso, simplemente copiamos todos los elementos restantes de la segunda matriz al resultado .

4. Implementación

Ahora veamos cómo implementarlo:

public static int[] merge(int[] foo, int[] bar) { int fooLength = foo.length; int barLength = bar.length; int[] merged = new int[fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo[fooPosition] < bar[barPosition]) { merged[mergedPosition++] = foo[fooPosition++]; } else { merged[mergedPosition++] = bar[barPosition++]; } } while (fooPosition < fooLength) { merged[mergedPosition++] = foo[fooPosition++]; } while (barPosition < barLength) { merged[mergedPosition++] = bar[barPosition++]; } return merged; }

Y procedamos con una breve prueba:

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int[] foo = { 3, 7 }; int[] bar = { 4, 8, 11 }; int[] merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar)); }

5. Complejidad

Atravesamos ambas matrices y elegimos el elemento más pequeño. Al final, copiamos el resto de elementos del foo o la matriz de barras . Entonces, la complejidad del tiempo se convierte en O (fooLength + barLength) . Hemos utilizado una matriz auxiliar para obtener el resultado. Entonces, la complejidad del espacio también es O (fooLength + barLength) .

6. Conclusión

En este tutorial, aprendimos cómo fusionar dos matrices ordenadas en una.

Como de costumbre, el código fuente de este tutorial se puede encontrar en GitHub.