Fusionar Ordenar en Java

1. Introducción

En este tutorial, veremos el algoritmo Merge Sort y su implementación en Java .

La clasificación por combinación es una de las técnicas de clasificación más eficientes y se basa en el paradigma de "divide y vencerás".

2. El algoritmo

La ordenación por fusión es un algoritmo de "divide y vencerás" en el que primero dividimos el problema en subproblemas. Cuando las soluciones para los subproblemas están listas, las combinamos para obtener la solución final al problema.

Este es uno de los algoritmos que se puede implementar fácilmente mediante la recursividad, ya que tratamos los subproblemas en lugar del problema principal.

El algoritmo se puede describir como el siguiente proceso de 2 pasos:

  • Dividir: en este paso, dividimos la matriz de entrada en 2 mitades , siendo el pivote el punto medio de la matriz. Este paso se lleva a cabo de forma recursiva para todas las medias matrices hasta que no queden más medias matrices para dividir.
  • Conquistar: En este paso, ordenamos y fusionamos las matrices divididas de abajo hacia arriba y obtenemos la matriz ordenada.

El siguiente diagrama muestra el proceso completo de clasificación de combinación para una matriz de ejemplo {10, 6, 8, 5, 7, 3, 4}.

Si echamos un vistazo más de cerca al diagrama, podemos ver que la matriz se divide de forma recursiva en dos mitades hasta que el tamaño se convierte en 1. Una vez que el tamaño se convierte en 1, los procesos de fusión entran en acción y comienzan a fusionar matrices de nuevo mientras se ordenan:

3. Implementación

Para la implementación, escribiremos una función mergeSort que toma la matriz de entrada y su longitud como parámetros. Esta será una función recursiva, por lo que necesitamos la base y las condiciones recursivas.

La condición base verifica si la longitud de la matriz es 1 y simplemente regresará. Para el resto de los casos se ejecutará la llamada recursiva.

Para el caso recursivo, obtenemos el índice medio y creamos dos arreglos temporales l [] y r [] . A continuación , se llama a la función mergeSort de forma recursiva para ambos subarreglos :

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Luego llamamos a la función de combinación que toma la entrada y tanto las submatrices como los índices inicial y final de ambas submatrices .

La función de combinación compara los elementos de ambas submatrices uno por uno y coloca el elemento más pequeño en la matriz de entrada.

Cuando llegamos al final de una de las submatrices, el resto de los elementos de la otra matriz se copian en la matriz de entrada, lo que nos da la matriz ordenada final:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

La prueba unitaria para el programa:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Complejidad

Como la ordenación por fusión es un algoritmo recursivo, la complejidad del tiempo se puede expresar como la siguiente relación recursiva:

T(n) = 2T(n/2) + O(n)

2T (n / 2) corresponde al tiempo requerido para ordenar las submatrices y O (n) tiempo para fusionar toda la matriz.

Cuando se resuelva, la complejidad del tiempo llegará a O (nLogn).

Esto es cierto para el peor, el promedio y el mejor caso, ya que siempre dividirá la matriz en dos y luego se fusionará.

La complejidad espacial del algoritmo es O (n) ya que estamos creando matrices temporales en cada llamada recursiva.

5. Conclusión

En este tutorial rápido, vimos el funcionamiento del algoritmo de clasificación por fusión y cómo podemos implementarlo en Java.

El código de trabajo completo está disponible en GitHub.