O que é o Merge Sort em C++?

Índice

• Introdução
• O que é ordenação por mesclagem em C++
• Abordagem Dividir e Conquistar
• Algoritmo de Classificação de Mesclagem
• Implementação de Merge Sort em C++
• Conclusão

1. Introdução

Os algoritmos de classificação na ciência da computação são usados ​​para organizar os dados em ordem crescente ou decrescente. Existem vários algoritmos de classificação com propriedades distintas disponíveis. Merge sort é um dos métodos em C++ que pode classificar os arrays.

2. O que é Merge Sort em C++

A classificação por mesclagem usa a técnica de dividir e conquistar que pode organizar os elementos de uma matriz. Ele também pode classificar a lista de elementos em C++. Ele divide a entrada em duas metades, classifica cada metade independentemente e depois as mescla na ordem correta.

3. Abordagem Dividir e Conquistar

O algoritmo de ordenação aplica uma estratégia de dividir e conquistar, que envolve particionar a matriz de entrada em submatrizes menores, resolvê-las separadamente e, em seguida, mesclar os resultados para produzir uma saída classificada. No caso do merge sort, o array é recursivamente dividido em duas metades até que reste apenas um elemento em cada metade.

4. Algoritmo de Classificação de Mesclagem

O algoritmo de classificação por mesclagem consiste em duas etapas principais: dividir e mesclar. As etapas são as seguintes:

4.1 Dividir

O algoritmo de classificação por mesclagem segue uma estratégia de divisão e conquista para classificar elementos em uma matriz.

• A primeira etapa do algoritmo verificará os elementos da matriz. Se contiver um elemento, já é considerado classificado e o algoritmo retornará o mesmo array sem nenhuma alteração.
• Se a matriz contiver mais de um elemento, o algoritmo procederá para dividi-la em duas metades: a metade esquerda e a metade direita.
• O algoritmo de classificação por mesclagem é então aplicado recursivamente às metades esquerda e direita do array, dividindo-os efetivamente em subarrays menores e classificando-os individualmente.
• Esse processo recursivo continua até que os subarrays contenham apenas um elemento cada (conforme a etapa 1), ponto em que eles podem ser mesclados para produzir um array de saída final classificado.

4.2 Mesclar

Agora veremos os passos para mesclar os arrays:

• A primeira etapa do algoritmo de classificação por mesclagem envolve a criação de uma matriz vazia.
• O algoritmo procede então para comparar os primeiros elementos das metades esquerda e direita da matriz de entrada.
• O menor dos dois elementos é adicionado à nova matriz e, em seguida, removido de sua respectiva metade da matriz de entrada.
• As etapas 2-3 são repetidas até que uma das metades seja esvaziada.
• Quaisquer elementos restantes na metade não vazia são adicionados à nova matriz.
• A matriz resultante agora está totalmente classificada e representa a saída final do algoritmo de classificação por mesclagem.

5. Implementação de Merge Sort em C++

Para implementar o merge sort em C++, dois métodos diferentes são seguidos. A complexidade de tempo de ambos os métodos é equivalente, mas o uso de subarrays temporários é diferente.

O primeiro método para o merge sort em C++ usa dois subarrays temporários, enquanto o segundo usa apenas um. Vale a pena notar que o tamanho total dos dois subarrays temporários no primeiro método é igual ao tamanho do array original no segundo método, então a complexidade do espaço permanece constante.

• Método 1 - Usando dois subarranjos temporários
• Método 2 - Usando um subarranjo temporário

Método 1 - Usando dois subarranjos temporários

Aqui está um exemplo de programa para classificação por mesclagem em C++ usando o Método 1, que usa dois subarrays temporários:

Neste programa, a função de mesclagem recebe três argumentos arr, l e r, que representam o array a ser classificado e mostram os índices do subarray que precisa ser mesclado. A função primeiro localiza os tamanhos dos dois subarrays a serem mesclados e, em seguida, cria dois subarrays temporários L e R para armazenar os elementos desses subarrays. Em seguida, compara os elementos em L e R e os mescla na matriz original chamada arr em ordem ascendente.

A técnica de dividir e conquistar é empregada pela função mergeSort para dividir o array em duas metades recursivamente até que haja apenas um elemento deixado de fora no subarray. Em seguida, mescla os dois subarrays em um subarray classificado. A função continua a mesclar os subarrays, a menos que classifique o array completo.

Na função principal, definimos um array arr com 6 elementos e chamamos a função mergeSort para classificá-lo. No final do código, a matriz classificada é impressa.

Método 2 - Usando um subarranjo temporário

Aqui está um programa de exemplo para classificação por mesclagem em C++ usando o Método 2, que usa um único subarray temporário:

Este programa é como o anterior, mas em vez de usar dois subarrays temporários L e R, ele usa um único subarray temporário temp. A função de mesclagem funciona da mesma forma que antes, mas em vez de copiar os dados para L e R, ela os copia para temp. Em seguida, mescla os elementos da matriz temporária de volta ao arr que é a matriz original.

A função mergeSort é a mesma de antes, exceto que usa temp em vez de L e R para armazenar o subarray temporário.

Na função principal, definimos um array arr com 6 elementos e chamamos a função mergeSort para classificá-lo. A execução do código termina imprimindo o array ordenado na tela.

Conclusão

Merge sort é um algoritmo que classifica os elementos da matriz e usa a técnica de dividir e conquistar e faz comparações entre os elementos. A classificação por mesclagem em C++ tem uma complexidade de tempo de O(n log n) e é particularmente eficaz para classificar matrizes grandes. Embora exija memória adicional para armazenar os subarrays mesclados, sua estabilidade o torna uma escolha popular para classificação.