Este blog é baseado na abordagem de dividir para conquistar. Merge Sort é um algoritmo de “dividir e conquistar” onde o problema é dividido em subproblemas e então mesclado para conquistar a solução. Este blog em Merge Sort em irá guiá-lo através dos tópicos abaixo em detalhes -
como clonar objeto em java
- O que é Merge Sort em Python?
- A abordagem de dividir e conquistar
- Implementando Merge Sort em Python
- Fluxograma para implementação de Merge Sort
- Vantagens e Uso
O que é Merge Sort em Python?
A classificação de mesclagem é baseada no algoritmo de divisão e conquista, em que a matriz de entrada é dividida em duas metades, depois classificada separadamente e mesclada de volta para chegar à solução. A função merge () é usada para mesclar os .
A abordagem de dividir e conquistar
- A matriz é dividida ao meio e o processo é repetido com cada metade até que cada metade tenha tamanho 1 ou 0.
- A matriz de tamanho 1 é classificada trivialmente.
- Agora as duas matrizes classificadas são combinadas em uma grande matriz. E isso continua até que todos os elementos sejam combinados e o array seja classificado.
Aqui está uma visualização do tipo de mesclagem para limpar a imagem para você
Matriz de entrada = [3,1,4,1,5,9,2,6,5,4]
Agora, vamos prosseguir para a implementação.
Implementando Merge Sort em Python
def mergeSort (nlist): print ('Dividindo', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (metade direita) i = j = k = 0 enquanto i Resultado:
$ python main.py
(‘Divisão’, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(‘Divisão’, [3, 1, 4, 1, 5])
(‘Divisão’, [3, 1])
(‘Divisão’, [3])
(‘Mesclar’, [3])
(‘Divisão’, [1])
(‘Mesclar’, [1])
(‘Mesclar’, [1, 3])
(‘Divisão’, [4, 1, 5])
(‘Divisão’, [4])
(‘Mesclar’, [4])
(‘Divisão’, [1, 5])
(‘Divisão’, [1])
(‘Mesclar’, [1])
(‘Divisão’, [5])
(‘Mesclando’, [5])
('Mesclando', [1, 5])
(‘Mesclar’, [1, 4, 5])
(‘Mesclar’, [1, 1, 3, 4, 5])
(‘Divisão’, [9, 2, 6, 5, 4])
(‘Divisão’, [9, 2])
(‘Divisão’, [9])
(‘Mesclando’, [9])
(‘Divisão’, [2])
(‘Mesclando’, [2])
(‘Mesclar’, [2, 9])
(‘Divisão’, [6, 5, 4])
(‘Divisão’, [6])
(‘Mesclando’, [6])
(‘Divisão’, [5, 4])
(‘Divisão’, [5])
(‘Mesclando’, [5])
(‘Divisão’, [4])
(‘Mesclar’, [4])
('Mesclando', [4, 5])
('Mesclando', [4, 5, 6])
(‘Mesclar’, [2, 4, 5, 6, 9])
(‘Mesclar’, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
como usar python no anaconda
Fluxograma para a implementação de Merge Sort
Vantagens e uso do Merge Sort
A maioria dos outros algoritmos tem um desempenho ruim com estruturas de dados sequenciais, como arquivos e listas vinculadas. Nessas estruturas, o acesso a um elemento aleatório leva um tempo linear, não um tempo constante regular. E a natureza da classificação de mesclagem torna mais fácil e rápido para essas estruturas de dados.Um dos melhores recursos da classificação por mesclagem é seu baixo número de comparações. Faz O (n * log (n)) número de comparações, mas o fator constante é bom quando comparado ao quicksort, o que o torna útil quando a função de comparação é uma operação lenta.Além disso, a abordagem de divisão e conquista da classificação por mesclagem a torna conveniente para o processamento paralelo.
Com isso, chegamos ao fim deste blog sobre “Como implementar Merge Sort em Python”. Espero que o conteúdo agregue algum valor ao seu conhecimento em Python. Para obter conhecimento aprofundado sobre Python e seus vários aplicativos, você pode se inscrever para com suporte 24/7 e acesso vitalício.