Combinar ordenación en Java

Merge Sort es un algoritmo clásico de divide y vencerás que recursivamente se llama a sí mismo en partes divididas por la mitad de la colección inicial. En este artículo, implementaremos Merge Sort en Java y lo compararemos con Quicksort.

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, de menor a mayor, etc. Esto hace que sea mucho más fácil comprender el datos ya que están lógicamente conectados en lugar de dispersos por todas partes.

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

Clasificación por combinación

Merge sort es un algoritmo de divide y vencerás, que recursivamente se llama a sí mismo en partes reducidas a la mitad de la colección inicial.

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

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

Esto generalmente se hace con colecciones que son demasiado grandes para cargarlas en la memoria, y las cargamos fragmento por fragmento a medida que se necesitan. 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 donde se cargan los elementos necesarios.

Dicho esto, Merge Sort tiene que lidiar con hacer que la carga y descarga sean óptimas, ya que puede volverse bastante lento 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 ni almacena los elementos en las direcciones de memoria de la colección que se le ha dado, sino que crea y devuelve una colección completamente nueva que es la versión ordenada de la que se le proporcionó.

Esta 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:

merge sort visual representation

Implementación

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

Empecemos con mergeSort():

1
2
3
4
5
6
7
8
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 sus punteros “bajo” y “alto”. Si el indicador ‘alto’ termina siendo menor o igual que el indicador ‘bajo’, simplemente ‘regresamos’.

De lo contrario, dividimos la matriz en dos mitades y llamamos a mergeSort desde el inicio de la matriz hasta el medio, y luego la llamamos desde el medio hasta el final.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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:

1
2
3
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
[1, 2, 4, 5, 6, 7, 7]

Complejidad del tiempo {#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 funcionó después de ordenar una matriz que contenía 10,000 enteros en orden aleatorio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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:


hora(s) Combinar Ordenar Primera ejecución 0.00551 Segunda ejecución 0.00852 Tercera Ejecución 0.00765 Cuarta Corrida 0.00543 Quinta carrera 0.00886 Sexta Corrida 0.00946 Séptima Ejecución 0.00575 Ocho Ejecutar 0.00765 Novena Corrida 0.00677 Décima Corrida 0.00550


Con un tiempo de ejecución promedio de 0.006s, es bastante rápido.

Conclusión

Merge sort es un algoritmo de divide y vencerás, que recursivamente se llama a sí mismo en partes reducidas 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 que clasifica, lo que puede causar problemas en 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 una complejidad de tiempo promedio de O(nlogn), junto con Quicksort, Timsort y Heapsort.me .me