Combinar orden en Java

¿Qué es la ordenación por combinación?

Merge Sort es el algoritmo más común para ordenar datos utilizando la técnica de " divide y vencerás ". En este algoritmo, el problema se divide en subproblemas y luego, después de ordenarlos, se fusionan. Digamos que tenemos una lista de números sin ordenar, el resultado de una clase para un tema determinado. Para ordenarlos en orden ascendente necesitaremos colocarlos en una lista comenzando de menor a mayor. En este algoritmo Merge Sort, la lista se dividirá en listas más pequeñas para ordenarlas en orden ascendente y luego fusionará los resultados para una mejor comprensión. Merge Sort en Java se puede explicar a través de un ejemplo de una matriz {6,9,8,2,4,1}, considérelo como el resultado de una prueba de clase sobre 10. La matriz (de resultados) se dividirá repetidamente en trozos más pequeños hasta que su tamaño sea 1. Luego, se lleva a cabo el proceso de fusión mientras se clasifican los números simultáneamente. Esto nos proporcionará un resultado que comienza con las notas más bajas hasta las más altas recibidas. Esta matriz se dividirá en dos matrices que contendrán 3 elementos cada una como se muestra a continuación en el paso 2 y seguirá dividiéndose hasta alcanzar la unidad en el paso 4 . Luego, el algoritmo Merge Sort comienza a ordenar los números paso a paso ( paso 5 ) y luego fusiona los números en una matriz más grande en los pasos 6 y 7 .

Implementación

En la implementación escribiremos código para el algoritmo de clasificación por combinación en Java. Las variables requeridas serán la matriz de entrada y la longitud de la matriz. Estos dos parámetros se utilizarán además para introducir más parámetros para crear la función de clasificación por combinación. Echemos un vistazo al siguiente fragmento para comprender el funcionamiento general del algoritmo Merge Sort en Java.

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

Primero, a través de la condición if, el principio y el final se utilizan para determinar el medio. Luego, en el siguiente paso, se crean 2 nuevos subarreglos comenzando desde el principio hasta el medio y el otro desde el medio +1 hasta el final. Estas matrices se dividen hasta que su longitud sea 1 y luego, a través de la función de combinación, las submatrices ordenadas Principio, Medio, Medio+1 y Fin se fusionan nuevamente para adquirir la solución.

Ejemplo

El siguiente código en Java explica el algoritmo de clasificación por combinación:

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

Producción

Conclusión

Merge Sort en Java es un algoritmo simple para adquirir una lista ordenada a partir de una lista de números sin ordenar. El método básico de ' divide y vencerás ' se aplica para acceder a la matriz ordenada desde una matriz no ordenada.