A classificação por mesclagem é semelhante ao algoritmo de classificação rápida, pois funciona no conceito de dividir para conquistar. É um dos algoritmos de classificação mais populares e eficientes. É o melhor exemplo da categoria de algoritmos de divisão para conquistar.
Ele divide a lista fornecida em duas metades, chama a si mesmo para as duas metades e depois mescla as duas metades classificadas. Nós definimos o mesclar() função usada para mesclar duas metades.
As sublistas são divididas repetidamente em metades até obtermos um único elemento cada. Em seguida, combinamos o par de listas de um elemento em duas listas de elementos, classificando-as no processo. Os dois pares de elementos classificados são mesclados nas quatro listas de elementos e assim por diante até obtermos a lista classificada.
Mesclar conceito de classificação
Vamos ver o seguinte diagrama de classificação de mesclagem.
Dividimos a lista fornecida em duas metades. A lista não poderia ser dividida em partes iguais, não importa nada.
A classificação por mesclagem pode ser implementada de duas maneiras - abordagem de cima para baixo e abordagem de baixo para cima. Usamos a abordagem de cima para baixo no exemplo acima, que é a classificação por mesclagem usada com mais frequência.
A abordagem bottom-up fornece mais otimização que definiremos mais tarde.
A parte principal do algoritmo é como combinamos as duas sublistas classificadas. Vamos mesclar as duas listas de mesclagem classificadas.
- A : [ 2 , 4, 7, 8]
- B: [ 1 , 3, 11]
- classificado: vazio
Primeiro, observamos o primeiro elemento de ambas as listas. Descobrimos que o primeiro elemento de B é menor, então adicionamos isso em nossa lista classificada e avançamos na lista B.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , onze]
- Ordenado: 1
Agora olhamos para o próximo par de elementos 2 e 3. 2 é menor, então o adicionamos à nossa lista classificada e avançamos para a lista.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , onze]
- Ordenado: 1
Continue este processo e terminaremos com a lista ordenada de {1, 2, 3, 4, 7, 8, 11}. Pode haver dois casos especiais.
10 de 50
E se ambas as sublistas tiverem os mesmos elementos - Nesse caso, podemos mover qualquer uma das sublistas e adicionar o elemento à lista classificada. Tecnicamente, podemos avançar na sublista e adicionar os elementos à lista ordenada.
Não temos mais nenhum elemento em uma sublista. Quando acabarmos em uma sublista, basta adicionar o elemento da segunda após a outra.
Devemos lembrar que podemos classificar o elemento em qualquer ordem. Classificamos a lista fornecida em ordem crescente, mas podemos facilmente classificar em ordem decrescente.
Implementação
O algoritmo de classificação por mesclagem é implementado usando a abordagem de cima para baixo. Pode parecer um pouco difícil, por isso iremos elaborar os detalhes de cada etapa. Aqui, implementaremos este algoritmo em dois tipos de coleções - lista de elementos inteiros (normalmente usada para introduzir classificação) e um objeto personalizado (um cenário mais prático e realista).
Classificando matriz
O conceito principal do algoritmo é dividir a (sub)lista em metades e classificá-las recursivamente. Continuamos o processo até terminarmos listas que possuem apenas um elemento. Vamos entender a seguinte função de divisão -
def merge_sort(array, left_index, right_index): if left_index >= right_index: return middle = (left_index + right_index)//2 merge_sort(array, left_index, middle) merge_sort(array, middle + 1, right_index) merge(array, left_index, right_index, middle)
Nosso foco principal é dividir a lista em subpartes antes que a classificação aconteça. Precisamos obter o valor inteiro, então usamos o operador // para nossos índices.
Vamos entender o procedimento acima seguindo as etapas.
- O primeiro passo é criar cópias das listas. A primeira lista contém as listas de [índice_esquerdo,...,meio] e o segundo de [meio+1,?,índice_direito] .
- Percorremos ambas as cópias da lista usando o ponteiro, selecionamos o menor valor dos dois valores e os adicionamos à lista ordenada. Depois de adicionarmos o elemento à lista e avançarmos na lista classificada de qualquer maneira.
- Adicione os elementos restantes na outra cópia à matriz classificada.
Vamos implementar a classificação por mesclagem no programa Python.
Programa Python
# Here, we are declaring the function to divide the lists in to the two sub lists # Here, we are passing the list1, left index, right index as the parameters def merge_sort(list1, left_index, right_index): if left_index >= right_index: # here, we are checking the if condition return middle = (left_index + right_index)//2 # Here, we are finding the middle of the given two numbers merge_sort(list1, left_index, middle) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, middle + 1, right_index) # Here, we are calling the merge sort function till the end of the list i.e., right index merge(list1, left_index, right_index, middle) # Here, we are calling the merge function to merge the divided list using the merge # sort function above # Here, we are defining a function for merge the list after dividing def merge(list1, left_index, right_index, middle): # Here, we are creating subparts of a lists left_sublist = list1[left_index:middle + 1] right_sublist = list1[middle+1:right_index+1] # Here, we are initializing the values for variables that we use to keep # track of where we are in each list1 left_sublist_index = 0 right_sublist_index = 0 sorted_index = left_index # Here, we are traversing the both copies until we get run out one element while left_sublist_index <len(left_sublist) 1 and right_sublist_index < len(right_sublist): # here, we are declaring a while loop if our left_sublist has the smaller element, put it in sorted part then move forward (by increasing pointer) left_sublist[left_sublist_index] checking condition, is true will enter block list1[sorted_index]="left_sublist[left_sublist_index]" left_sublist_index="left_sublist_index" + otherwise add into right sublist else: moving sorted_index="sorted_index" go through remaining elements them len(left_sublist): len(right_sublist):# list1="[44," 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] print('the given list before performing merge sort is: ', list1) this input unsorted array by user merge_sort(list1, 0, len(list1) -1) after is:', printing amd functions pre> <p> <strong>Output:</strong> </p> <pre> The given list before performing the merge sort is: [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] The given list after performing the merge sort is: [1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74] </pre> <h2>Sorting Custom Objects</h2> <p>We can also sort the custom objects by using the <a href="/python-tutorial-python-programming-language">Python</a> class. This algorithm is almost similar to the above but we need to make it more versatile and pass the comparison function.</p> <p>We will create a custom class, Car and add a few fields to it. We make few changes in the below algorithm to make it more versatile. We can do this by using the lambda functions.</p> <p>Let's understand the following example.</p> <h3>Python Program</h3> <pre> class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format('Make: {}, Model: {}, Year: {}', self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print('cars sorted by year:') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let's understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)></pre></len(left_sublist)> Classificando objetos personalizados
Também podemos classificar os objetos personalizados usando o Pitão aula. Este algoritmo é quase semelhante ao anterior, mas precisamos torná-lo mais versátil e passar a função de comparação.
o que é 25 de 100
Criaremos uma classe personalizada, Car, e adicionaremos alguns campos a ela. Fazemos algumas alterações no algoritmo abaixo para torná-lo mais versátil. Podemos fazer isso usando as funções lambda.
Vamos entender o exemplo a seguir.
Programa Python
class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format('Make: {}, Model: {}, Year: {}', self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print(\'cars sorted by year:\') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:\') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let's understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)> Otimização
Podemos melhorar o desempenho do algoritmo de classificação por mesclagem. Primeiro, vamos entender a diferença entre a classificação de mesclagem de cima para baixo e de baixo para cima. A abordagem ascendente classifica os elementos das listas adjacentes iterativamente, enquanto a abordagem descendente divide as listas em duas metades.
A lista fornecida é [10, 4, 2, 12, 1, 3], em vez de dividi-la em [10], [4], [2], [12], [1], [3] - nós dividimos nas sublistas que já podem ser classificadas: [10, 4], [2], [1, 12], [3] e agora estão prontas para classificá-las.
A classificação por mesclagem é um algoritmo ineficiente tanto no tempo quanto no espaço para sublistas menores. Portanto, a classificação por inserção é um algoritmo mais eficiente do que a classificação por mesclagem para sublistas menores.
Conclusão
Merge sort é um algoritmo popular e eficiente. É um algoritmo mais eficiente para listas grandes. Não depende de quaisquer decisões infelizes que levem a tempos de execução ruins.
Há um grande demérito na classificação por mesclagem. Ele usa a memória adicional usada para armazenar cópias temporárias de listas antes de mesclá-las. No entanto, a classificação por mesclagem é amplamente utilizada no software. Seu desempenho é rápido e produz excelente resultado.
Discutimos brevemente o conceito de classificação por mesclagem e o implementamos tanto em uma lista de inteiros simples quanto em objetos personalizados por meio de uma função lambda usada para comparação.