Fusionar Ordenar en Java

Introducción

La clasificación es un aspecto crucial de la digestión de datos. Para nosotros, los humanos, es mucho más natural ordenar las cosas que tienen algo en común, como la fecha de publicación, el orden alfabético, los artículos que pertenecen a un autor, del más pequeño al más grande, etc. Esto hace que sea mucho más fácil comprender los datos ya que conectados lógicamente en lugar de dispersos por todas partes.

Y lo que es igualmente importante, las matrices ordenadas son más fáciles de utilizar para las computadoras. Por ejemplo, una matriz ordenada se puede buscar mucho más rápido, como con el búsqueda binaria algoritmo, que se ejecuta en tiempo O (logn). Un algoritmo como este simplemente no funciona sin una matriz ordenada.

Combinar ordenar

Fusionar ordenación es una divide y conquistaras algoritmo, que se invoca recursivamente a sí mismo en porciones divididas a la mitad de la colección inicial.

Dicho esto, suena mucho a Ordenación rápida, que también particiona la colección y luego se llama a sí mismo de forma recursiva en las colecciones particionadas (que normalmente son mitades).

La principal diferencia es el hecho de que Quicksort es un algoritmo de clasificación interno, en el lugar, mientras que Merge Sort es un algoritmo de clasificación externo y fuera de lugar.

Esto generalmente se hace con colecciones que son demasiado grandes para cargarlas en la memoria, y las cargamos fragmento a fragmento según sea necesario. Por lo tanto, Merge Sort no necesita almacenar toda la colección en la memoria desde la cual puede acceder fácil y aleatoriamente a todos y cada uno de los elementos en un momento dado. Más bien, la colección se puede almacenar en un lugar externo, como un disco (o hace mucho más tiempo, una cinta), desde el cual se cargan los elementos necesarios.

Dicho esto, Merge Sort tiene que lidiar con hacer que dicha carga y descarga sea óptima, ya que puede volverse bastante lenta con grandes colecciones.

Como se mencionó anteriormente, Merge Sort es un algoritmo de clasificación «fuera de lugar». Lo que esto significa es que Merge Sort no ordena y almacena los elementos en las direcciones de memoria de la colección que se le ha asignado, sino que crea y devuelve una colección completamente nueva que es la versión ordenada de la que se le proporcionó.

Ésta es una distinción importante debido al uso de la memoria. Para arreglos muy grandes, esto sería una desventaja porque los datos se duplicarán, lo que puede causar problemas de memoria en algunos sistemas.

Aquí hay una representación visual de cómo funciona:

Implementación

Para facilitar el algoritmo, usaremos dos métodos: mergeSort() que dividirá la colección y se llamará recursivamente a sí mismo, y a su método auxiliar, merge() que fusionará los resultados en el orden correcto.

Comencemos con mergeSort():

public static void mergeSort(int[] array, int low, int high) {
    if (high <= low) return;

    int mid = (low+high)/2;
    mergeSort(array, low, mid);
    mergeSort(array, mid+1, high);
    merge(array, low, mid, high);
}

Esta parte es bastante sencilla: proporcionamos una matriz para ordenar y es low y high punteros. Si el high puntero termina siendo más bajo o igual al low puntero, simplemente return.

De lo contrario, dividimos la matriz en dos mitades y llamamos mergeSort desde el principio de la matriz hasta el medio, y luego llámelo desde el medio hasta el final.

En última instancia, llamamos al merge() método, que fusiona los resultados en una matriz ordenada:

public static void merge(int[] array, int low, int mid, int high) {
    // Creating temporary subarrays
    int leftArray[] = new int[mid - low + 1];
    int rightArray[] = new int[high - mid];

    // Copying our subarrays into temporaries
    for (int i = 0; i < leftArray.length; i++)
        leftArray[i] = array[low + i];
    for (int i = 0; i < rightArray.length; i++)
        rightArray[i] = array[mid + i + 1];

    // Iterators containing current index of temp subarrays
    int leftIndex = 0;
    int rightIndex = 0;

    // Copying from leftArray and rightArray back into array
    for (int i = low; i < high + 1; i++) {
        // If there are still uncopied elements in R and L, copy minimum of the two
        if (leftIndex < leftArray.length && rightIndex < rightArray.length) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
               array[i] = leftArray[leftIndex];
               leftIndex++;
            } else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        } else if (leftIndex < leftArray.length) {
            // If all elements have been copied from rightArray, copy rest of leftArray
            array[i] = leftArray[leftIndex];
            leftIndex++;
        } else if (rightIndex < rightArray.length) {
            // If all elements have been copied from leftArray, copy rest of rightArray
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

Ejecutando el siguiente fragmento de código:

int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));

Nos dará una matriz ordenada:

[1, 2, 4, 5, 6, 7, 7]

Complejidad del tiempo

La complejidad de tiempo promedio y en el peor de los casos de Merge Sort es O (nlogn), lo cual es justo para un algoritmo de clasificación. Así es como se realizó después de ordenar una matriz que contiene 10,000 enteros en orden aleatorio:

int[] array = new int[10000];
for (int i = 0; i < array.length; i++) {
    array[i] = i;
}

// Shuffle array
Collections.shuffle(Arrays.asList(array));

// Print shuffled collection
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
}

long startTime = System.nanoTime();
mergeSort(array, 0, array.lenth-1);
long endTime = System.nanoTime();

// Print sorted collection
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
}

System.out.println();

// Print runtime in nanoseconds
System.out.println("Merge Sort runtime: " + (endTime - startTime));

Y aquí están los resultados en segundos después de ejecutarlo 10 veces:

tiempo (s) Fusionar Ordenar

Con un tiempo de ejecución medio de 0,006 s, es bastante rápido.

Conclusión

Fusionar ordenación es una divide y conquistaras algoritmo, que se invoca recursivamente a sí mismo en porciones divididas a la mitad de la colección inicial.

Otra cosa a tener en cuenta es que Merge Sort es un algoritmo de clasificación «fuera de lugar». Esto significa que requiere espacio adicional para almacenar los elementos de su clasificación, lo que puede causar problemas a los sistemas con limitaciones de memoria. Esta es una compensación de usar este algoritmo.

Aunque es uno de los algoritmos de clasificación más rápidos y eficientes con la complejidad de tiempo promedio de O (nlogn), junto con Quicksort, Timsort y Heapsort.me