Introdução à classificação de mesclagem em Java
Programa para Merge Sort em Java é um dos algoritmos mais amplamente utilizados e eficientes. A classificação por mesclagem é baseada na técnica de dividir e conquistar, que envolve dividir um determinado problema em vários subproblemas e resolver cada subproblema independentemente. Quando os subproblemas são resolvidos, combinamos seus resultados para obter a solução final para o problema. O algoritmo de ordenação por mesclagem pode ser implementado usando recursão, pois envolve o trabalho com subproblemas, em vez do principal problema.
Como funciona a classificação de mesclagem?
Vamos considerar uma matriz não classificada que precisa ser classificada usando o algoritmo de classificação por mesclagem. Aqui estão as etapas envolvidas na classificação de uma matriz com valores: 18, 8, 4, 13, 10, 12, 7 e 11:
- O primeiro passo envolve encontrar um elemento dinâmico com base no qual nossa matriz de entrada será dividida em sub-matrizes.
- Vamos considerar que o elemento 13 é escolhido como o pivô, portanto, a matriz original será dividida em duas sub-matrizes. O primeiro subarray conterá 18, 8, 4, 13 e o segundo subarray conterá os elementos restantes 10, 12, 7, 11.
- As sub-matrizes obtidas na etapa 2 são subdivididas ainda como na etapa 1 e isso continua.
- Depois que a matriz principal é dividida em sub-matrizes com elementos únicos, começamos a mesclar essas sub-matrizes novamente, para que os elementos mesclados estejam na ordem de classificação.
- Aqui está como a divisão e conquista real funciona:
Programa para Mesclar Classificação em Java
Aqui está um exemplo de código que mostra a implementação da classificação de mesclagem em java:
Código:
package com.edubca.sorting;
public class MergeSort (
private int() array;
private int() tempMergedArr;
private int length;
public static void main(String a())(
int() inputArr = (18, 8, 4, 13, 10, 12, 7, 11);
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for(int i:inputArr)(
System.out.print(i + " ");
)
)
public void sort(int inputArr()) (
this.array = inputArr;
this.length = inputArr.length;
this.tempMergedArr = new int(length);
performMergeSort(0, length - 1);
)
private void performMergeSort(int lowerIndex, int higherIndex) (
if (lowerIndex < higherIndex) (
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Sort the left side of the array call performMergeSort recursively
performMergeSort(lowerIndex, middle);
// Sort the right side of the array call performMergeSort recursively
performMergeSort(middle + 1, higherIndex);
// Merge subparts using a temporary array
mergeData(lowerIndex, middle, higherIndex);
)
)
private void mergeData (int lowerIndex, int middle, int higherIndex) (
for (int i = lowerIndex; i <= higherIndex; i++) (
tempMergedArr(i) = array(i);
)
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) (
if (tempMergedArr(i) <= tempMergedArr(j)) (
array(k) = tempMergedArr(i);
i++;
) else (
array(k) = tempMergedArr(j);
j++;
)
k++;
)
while (i <= middle) (
array(k) = tempMergedArr(i);
k++;
i++;
)
)
)
O código acima produzirá uma matriz classificada como saída.
Resultado:
Quando devemos usar a classificação de mesclagem?
A classificação de mesclagem pode ser usada nos seguintes cenários:
- Quando a estrutura de dados a ser classificada não suporta acesso aleatório, a classificação de mesclagem pode ser útil e eficiente.
- Quando um alto nível de paralelismo é necessário, a classificação de mesclagem pode ser usada, pois diferentes subproblemas podem ser resolvidos independentemente, usando vários processos em execução em paralelo.
- A classificação de mesclagem é mais rápida ao trabalhar com listas vinculadas porque os ponteiros podem ser facilmente alterados ao mesclar as listas.
- A classificação de mesclagem pode ser considerada como uma classificação estável, o que significa que o mesmo elemento em uma matriz mantém suas posições originais uma em relação à outra. Nos casos em que é necessária alta estabilidade, pode-se optar pela classificação por mesclagem.
Análise de complexidade da classificação de mesclagem
Abaixo a complexidade da análise de pontos da classificação por mesclagem:
- A classificação por mesclagem é um algoritmo recursivo e sua complexidade de tempo é O (n * log n) nos três casos (pior, melhor e médio), pois a classificação por mesclagem divide a matriz em duas metades iguais e leva tempo linear para mesclá-las.
- A complexidade espacial da classificação por mesclagem é O (n), pois opera na abordagem recursiva. Portanto, a classificação por mesclagem pode ser considerada como um algoritmo rápido, com espaço e tempo eficiente.
Comparando a classificação de mesclagem com outros algoritmos
Os pontos abaixo comparam a classificação de mesclagem com outros algoritmos:
- A classificação de heap tem a mesma complexidade de tempo que a classificação de mesclagem, mas requer apenas espaço auxiliar O (1) em vez do O (n) da classificação de mesclagem. Portanto, a classificação de heap é mais eficiente em termos de espaço que a classificação de mesclagem.
- As implementações de Classificação Rápida geralmente superam a classificação de mesclagem para classificar matrizes baseadas em RAM.
- A classificação de mesclagem supera os algoritmos de classificação rápida e de classificação de pilha ao trabalhar com a lista vinculada, pois os ponteiros podem ser facilmente alterados.
Programa de conclusão para classificação de mesclagem em Java
A partir do artigo, conclui-se que a classificação por mesclagem é um conceito importante para entender quando se trata de algoritmos.
Artigos recomendados
Este é um guia para o Program for Merge Sort em Java. Aqui discutimos como deve funcionar, seu uso, o programa Merge Sort etc. Você também pode consultar outros artigos relacionados para saber mais.
- Mesclar classificação em Java
- Mesclar algoritmos de classificação em Java
- Heap Classificar em C
- Heap Sort In Java
- Ferramentas de implantação Java
- Heap Sort em Python
- Algoritmos de classificação rápida em Java
- Os 6 principais algoritmos de classificação em JavaScript
- Os 6 principais algoritmos de classificação em Python