Mesclar classificação em Java

O que é classificação por mesclagem?

O Merge Sort é o algoritmo mais comum para classificação de dados usando a técnica “ dividir e conquistar ”. Neste algoritmo, o problema é dividido em subproblemas e após a classificação eles são mesclados. Digamos que temos uma lista de números não ordenados, resultado de uma aula de uma determinada disciplina. Para classificá-los em ordem crescente, precisaremos colocá-los em uma lista começando do menor para o maior. Neste algoritmo Merge Sort, a lista será dividida em listas menores para classificá-las em ordem crescente e então mesclará os resultados para melhor compreensão. Merge Sort em Java pode ser explicado através de um exemplo de array {6,9,8,2,4,1}, considere-o como resultado de um teste de classe de 10. O array (de resultados) será dividido repetidamente em pedaços menores até que seu tamanho seja 1. Em seguida, o processo de fusão ocorre enquanto os números são classificados simultaneamente. Isso nos fornecerá um resultado que começa com as notas mais baixas até as notas mais altas recebidas. Este array será dividido em dois arrays que conterão 3 elementos cada, conforme mostrado abaixo na etapa 2 e continuará se dividindo até que a unidade seja alcançada na etapa 4 . Em seguida, o algoritmo Merge Sort começa a classificar os números uma etapa de cada vez ( etapa 5 ) e depois mescla os números em uma matriz maior nas etapas 6 e 7 .

Implementação

Na implementação escreveremos código para o algoritmo de classificação por mesclagem em Java. As variáveis ​​​​necessárias serão a matriz de entrada e o comprimento da matriz. Esses dois parâmetros serão usados ​​posteriormente para introduzir outros parâmetros para criar a função de classificação por mesclagem. Vamos dar uma olhada no trecho abaixo para entender o funcionamento geral do algoritmo Merge Sort em 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

Primeiro, através da condição if, Início e Fim são usados ​​para determinar o Meio. Então, na próxima etapa, 2 novos subarrays são criados começando do Início até o Meio e o outro começando do Meio +1 até o Fim. Essas matrizes são divididas até que seu comprimento se torne 1 e, em seguida, por meio da função Merge, as submatrizes classificadas Início, Meio, Meio + 1 e Fim são mescladas novamente para adquirir a solução.

Exemplo

O código a seguir em Java explica o algoritmo de classificação por mesclagem:

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");
    }
}

Saída

Conclusão

Merge Sort em Java é um algoritmo simples para adquirir uma lista classificada de uma lista não classificada de números. O método básico de ' dividir e conquistar ' é aplicado para acessar o array classificado a partir de um array não classificado.