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

    Primer intento0,00551
    Segunda ejecuci贸n0,00852
    Tercera carrera0,00765
    Cuarta carrera0,00543
    Quinta carrera0,00886
    Sexta carrera0,00946
    S茅ptima carrera0,00575
    Ocho correr0,00765
    Novena carrera0,00677
    D茅cima carrera0,00550

    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

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *