Programa Python para Merge Sort

Como uma linguagem de programação multiparadigma com uma abordagem de design estruturada e orientada a objetos e sintaxe e gramática simples e organizadas, o Python está emergindo rapidamente como a linguagem de escolha para programadores que trabalham em projetos de complexidade e escala variadas.

O Python fornece uma biblioteca modular de algoritmos pré-construídos que permite que seus usuários executem várias operações que podem ajudá-los a realizar suas tarefas por si mesmos ou servir como uma etapa no caminho para alcançar um objetivo maior e mais complexo. Um dos algoritmos mais populares é aquele que habilita a funcionalidade Merge Sort.

O que é o Merge Sort?

É uma técnica de classificação de uso geral que permite aos usuários pegar um conjunto de dados aleatório de qualquer tipo e de qualquer fonte e dividi-lo em estágios repetitivos até que seja dividido em seus componentes individuais - uma técnica recursiva, comumente chamada de ' método de dividir e conquistar.

O algoritmo então reúne os componentes individuais – novamente em estágios repetitivos – mas os classifica em uma sequência lógica pré-decidida em cada estágio ao longo do caminho, usando a comparação básica e a troca até que toda a série de dados seja reconstituída na sequência lógica desejada .

Confira nossos outros cursos de ciência de dados em upGrad.

Técnica de Dividir e Conquistar

Tome, por exemplo, um conjunto de dados aleatório de letras do alfabeto: N, H, V, B, Q, D, Z, R.

Passo 1 : O conjunto de dados original primeiro é dividido em dois grupos da seguinte forma:

N, H, V, B Q, D, Z, R

Passo 2 : Ambos os arrays resultantes são subdivididos da seguinte forma:

N, H V, B Q, D Z, R

Etapa 3 : Finalmente, todas as quatro matrizes são cuspidas até que toda a série de dados seja dividida em seus componentes individuais:

N H V B Q D Z R

O processo é revertido e os pontos de dados individuais agora começam a se fundir de maneira gradual. Mas, ao longo desse processo de fusão, cada elemento em cada subarray é avaliado e trocado para que eles se classifiquem em uma sequência lógica (ordem alfabética), da seguinte forma:

Etapa 4 : Os elementos individuais se fundem em pares enquanto trocam de posição conforme necessário para formar a sequência correta:

H, N B, V D, Q R, Z

Etapa 5 : O processo recursivo de mesclagem e classificação continua na próxima iteração:

B, H, N, V ​​D, Q, R, Z

Passo 6 : Toda a série de dados é finalmente reconstituída em sua ordem alfabética lógica:

B, D, H, N, Q, R, V, Z

Explore nossos cursos populares de ciência de dados

Implementações de classificação de mesclagem

Existem duas abordagens para a implementação do Merge Sort em Python. A abordagem de cima para baixo e a abordagem de baixo para cima.

Abordagem de cima para baixo:

A abordagem de cima para baixo mais comumente usada é a descrita acima. Leva mais tempo e consome mais memória e, portanto, é ineficiente ao trabalhar com conjuntos de dados menores. No entanto, é muito mais confiável, principalmente quando aplicado a grandes conjuntos de dados.

Leia nossos artigos populares sobre ciência de dados

Código de entrada:

def merge_sort (inp_arr):

tamanho = len(inp_arr)

se tamanho > 1:

meio = tamanho // 2

esquerda_arr = inp_arr(:meio)

rIght_arr = inp_arr(meio:)

merge_sort(left_arr)

merge _sort(right_arr)

eu = 0

j = 0

k = 0

(Onde i e j são os iteradores para percorrer as metades esquerda e direita da série de dados, respectivamente, e k é o iterador da série de dados geral).

tamanho_esquerdo = len(arr_esquerdo)

tamanho_direito = len(arr_direito)

enquanto i < tamanho_esquerdo e j < tamanho direito:

if left_arr(i) < right_arr (j):

inp_arr(k) – left_arr(i)

eu >= 1

outro:

inp_arr(k) = right_arr (j)

j += 1

k += 1

enquanto eu <tamanho_esquerdo:

inp_arr (k) = left_arr(i)

eu += 1

k += 1

enquanto j < tamanho_direito:

inp_arr (k) = right_arr(j)

j += 1

k += 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:Matriz de entrada:\n”)

print(inp_arr)

merge_sort (inp_arr)

print(“Matriz Ordenada:\n”)

imprimir (inp_arr)

Saída:

Matriz de entrada: N, H, V, B, Q, D, Z, R

Matriz de saída: B, D, H, N, Q, R, V, Z

Abordagem de baixo para cima:

A abordagem de baixo para cima é mais rápida, usa menos memória e funciona de forma eficiente com conjuntos de dados menores, mas pode ter problemas ao trabalhar com grandes conjuntos de dados. Portanto, é usado com menos frequência.

Código de entrada:

def merge(esquerda, direita):

resultado = [] x, y = 0, 0

para k no intervalo(0, len(esquerda) + len(direita)):

if i == len(left): # se no final do 1º tempo,

result.append(right[j]) # soma todos os valores da 2ª parte

j += 1

elif j == len(direita): # se no final do 2º tempo,

result.append(left[x]) # soma todos os valores da 1ª metade

eu += 1

elif direita[j] < esquerda[i]:

result.append(right[j])

j += 1

outro:

result.append(esquerda[i])

eu += 1

resultado de retorno

def mergesort(ar_list):

comprimento = len(ar_list)

tamanho = 1

enquanto tamanho < comprimento:

size+=size # inicializa em 2 como descrito

para pos in range(0, length, size):

início = pos

mid = pos + int(tamanho/2)

fim = pos + tamanho

esquerda = lista_ar[início: meio] direita = lista_ar[meio: fim]

ar_list[start:end] = merge(esquerda, direita)

retornar ar_list

ar_list = [N, H, V, B, Q, D, Z, R] print(mergesort(ar_list))

Saída:

Matriz de entrada: N, H, V, B, Q, D, Z, R

Matriz de saída: B, D, H, N, Q, R, V, Z

Implementação de Merge Sort aplicada a conjuntos de dados mais complexos da vida real

Vamos aplicar a abordagem de cima para baixo a quatro veículos off-road aleatórios na Índia:

Código de entrada:

Classe Carro:

def __init__(auto, marca, modelo, preço):

self.brand = marca

self.model = modelo

auto.preço = preço

def __str__(auto):

return str.format(“Marca: {}, Modelo: {}, Preço: {}”, self.brand,

auto.modelo, auto.preço)

def merge(list1, i, j, k, comp_fun):

cópia_esquerda = lista1[i:k + 1]

r_sublista = lista1[k+1:r+1]

left_copy_index = 0

j_sublist_index = 0

índice_classificado = i

enquanto left_copy_index < len(left_copy) ej_sublist_index <

len(j_sublist):

if comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

senão :

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

índice_classificado = índice_classificado + 1

while left_copy_index < len(left_copy):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

índice_classificado = índice_classificado + 1

while j_sublist_index < len(j_sublist):

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

índice_classificado = índice_classificado + 1

def merge_sort(lista1, i, j, comp_fun):

se i >= j:

Retorna

k = (i + j)//2

merge_sort(lista1, i, k, comp_fun)

merge_sort(lista1, k + 1, j, comp_fun)

merge(lista1,i,j,k,comp_fun)

carro1 = Carro("Jeep", "Wrangler", 0,58)

carro2 = Carro(“Ford”, “Esforço”, 0,35)

carro3 = Carro(“Jaguar Land Rover”, “Range Rover Sport”, 1.76)

carro4 = Carro(“Mercedes Benz”, “Classe G”, 2,42)

lista1 = [carro1, carro2, carro3, carro4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)

print (“Carros classificados por marca:”)

para o carro nalista1:

imprimir (carro)

imprimir ()

merge_sort(lista1, 0, len(lista1) -1, lambda carroA, carroB: carroA.preço< carroB.preço)

print (“Carros ordenados por preço:”)

para o carro nalista1:

imprimir (carro)

Saída:

Carros classificados por marca:

Ford Endeavor

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedes Benz classe G

Carros classificados por preço:

Ford Endeavor

Jeep Wrangler

Jaguar Land Rover Range Rover

Mercedes Benz classe G

Você pode aprender os aspectos teóricos e práticos do Python com o Certificado Profissional upGrad em Ciência de Dados e Análise de Negócios da Universidade de Maryland. Este curso ajuda você a aprender Python do zero. Mesmo que você seja novo em programação e codificação, o upGrad oferece um curso preparatório de duas semanas para que você possa aprender os fundamentos da programação. você aprenderá sobre várias ferramentas como Python, SQL, enquanto trabalha em vários projetos do setor.

Planeje sua carreira de desenvolvimento de software agora!

Candidate-se ao programa de certificação profissional em ciência de dados e análise de negócios