Programma Python per Merge Sort

Come linguaggio di programmazione multi-paradigma con un approccio di progettazione strutturato e orientato agli oggetti e una sintassi e una grammatica semplici e ordinate, Python sta rapidamente emergendo come il linguaggio preferito dai programmatori che lavorano su progetti di varia complessità e scala.

Python fornisce una libreria modulare di algoritmi predefiniti che consente ai suoi utenti di eseguire varie operazioni che possono aiutarli a raggiungere il loro compito in sé e per sé o servire come passo lungo la strada per raggiungere un obiettivo più ampio e più complesso. Uno degli algoritmi di questo tipo più popolari è quello che abilita la funzionalità Merge Sort.

Che cos'è Merge Sort?

È una tecnica di ordinamento generica che consente agli utenti di prendere un set di dati casuale di qualsiasi tipo e da qualsiasi fonte e di dividerlo in fasi ripetitive fino a quando non viene scomposto nei suoi singoli componenti: una tecnica ricorsiva, comunemente indicata come " metodo divide et impera.

L'algoritmo quindi mette insieme i singoli componenti, sempre in fasi ripetitive, ma li ordina in una sequenza logica prestabilita in ogni fase lungo il percorso, utilizzando il confronto di base e lo scambio fino a quando l'intera serie di dati non viene ricostituita nella sequenza logica desiderata .

Dai un'occhiata agli altri nostri corsi di scienza dei dati su upGrad.

Tecnica divide et impera

Prendi, ad esempio, un set di dati casuale di lettere dell'alfabeto: N, H, V, B, Q, D, Z, R.

Passaggio 1 : il set di dati originale viene prima suddiviso in due gruppi come segue:

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

Passaggio 2 : entrambi gli array risultanti vengono ulteriormente suddivisi come segue:

N, HV , BQ, DZ, R

Passaggio 3 : infine, tutti e quattro gli array vengono ulteriormente sputati fino a quando l'intera serie di dati non viene scomposta nei suoi singoli componenti:

N H V B Q D Z R

Il processo quindi si inverte e i singoli punti dati ora iniziano a fondersi in modo graduale. Ma nel corso di questo processo di fusione, ogni elemento in ogni sottoarray viene valutato e scambiato in modo che si risolva in una sequenza logica (ordine alfabetico), come segue:

Passaggio 4 : i singoli elementi si uniscono in coppie mentre si scambiano le posizioni come richiesto per formare la sequenza corretta:

H, NB , VD, QR , Z

Passaggio 5 : il processo ricorsivo di fusione e ordinamento continua fino all'iterazione successiva:

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

Passaggio 6 : l'intera serie di dati viene infine ricostituita nel suo ordine logico alfabetico:

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

Esplora i nostri popolari corsi di scienza dei dati

Unisci implementazioni di ordinamento

Esistono due approcci all'implementazione di Merge Sort in Python. L'approccio top-down e l'approccio bottom-up.

Approccio dall 'alto verso il basso:

L'approccio top-down più comunemente utilizzato è quello sopra descritto. Richiede più tempo e utilizza più memoria ed è quindi inefficiente quando si lavora con set di dati più piccoli. Tuttavia, è molto più affidabile, in particolare se applicato a set di dati di grandi dimensioni.

Leggi i nostri popolari articoli sulla scienza dei dati

Codice di input:

def merge_sort (inp_arr):

dimensione = len(inp_arr)

se dimensione > 1:

mezzo = taglia // 2

left_arr = inp_arr(:middle)

destra_arr = inp_arr(centro:)

merge_sort(sinistra_arr)

unisci _ordina(right_arr)

io = 0

j = 0

K = 0

(Dove i e j sono gli iteratori per attraversare rispettivamente la metà sinistra e destra della serie di dati e k è l'iteratore della serie di dati complessiva).

dimensione_sinistra = len(arr_sinistra)

dimensione_destra = len(arr_destra)

mentre i < dimensione_sinistra e j < dimensione destra:

se arr_sinistra(i) < arr_destra (j):

inp_arr(k) – left_arr(i)

io >= 1

altro:

inp_arr(k) = right_arr (j)

j += 1

k += 1

mentre i < dimensione_sinistra:

inp_arr (k) = left_arr(i)

io += 1

k += 1

mentre j < dimensione_destra:

inp_arr (k) = right_arr(j)

j += 1

k += 1

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

print(:Input Array:\n”)

stampa(inp_arr)

merge_sort (inp_arr)

print("Array ordinato:\n")

stampa (inp_arr)

Produzione:

Array di input: N, H, V, B, Q, D, Z, R

Array di uscita: B, D, H, N, Q, R, V, Z

Approccio dal basso:

L'approccio dal basso verso l'alto è più rapido, utilizza meno memoria e funziona in modo efficiente con set di dati più piccoli, ma può incorrere in problemi quando si lavora con set di dati di grandi dimensioni. È quindi usato meno frequentemente.

Codice di input:

def unisci(sinistra, destra):

risultato = [] x, y = 0, 0

per k in range(0, len(sinistra) + len(destra)):

if i == len(sinistra): # if alla fine del 1° tempo,

result.append(right[j]) # somma tutti i valori della seconda metà

j += 1

elif j == len(right): # if alla fine del 2° tempo,

result.append(left[x]) # somma tutti i valori della prima metà

io += 1

elif destra[j] < sinistra[i]:

risultato.append(right[j])

j += 1

altro:

risultato.append(left[i])

io += 1

risultato di ritorno

def mergesort(ar_list):

lunghezza = len(ar_list)

dimensione = 1

mentre dimensione < lunghezza:

size+=size # inizializza a 2 come descritto

per pos in range(0, lunghezza, dimensione):

inizio = pos

mid = pos + int(dimensione / 2)

fine = posizione + dimensione

left = ar_list[ start : mid ] right = ar_list[ mid : end ]

ar_list[start:end] = merge(sinistra, destra)

restituisce ar_list

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

Produzione:

Array di input: N, H, V, B, Q, D, Z, R

Array di uscita: B, D, H, N, Q, R, V, Z

Implementazione Merge Sort applicata a set di dati reali più complessi

Applichiamo l'approccio dall'alto verso il basso a quattro veicoli fuoristrada casuali in India:

Codice di input:

classe Auto:

def __init__(self, marca, modello, prezzo):

self.marca = marca

self.modello = modello

self.prezzo = prezzo

def __str__(self):

return str.format("Marca: {}, Modello: {}, Prezzo: {}", self.brand,

self.modello, self.prezzo)

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

copia_sinistra = lista1[i:k + 1]

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

left_copy_index = 0

j_sublist_index = 0

indice_ordinato = i

mentre left_copy_index < len(left_copy) ej_sublist_index <

len(j_sublista):

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

lista1[indice_ordinato] = copia_sinistra[indice_copia_sinistra]

left_copy_index = left_copy_index + 1

altro :

lista1[indice_ordinato] = j_sottolista[j_sottolista_indice]

j_sublist_index = j_sublist_index + 1

indice_ordinato = indice_ordinato + 1

while left_copy_index < len(left_copy):

lista1[indice_ordinato] = copia_sinistra[indice_copia_sinistra]

left_copy_index = left_copy_index + 1

indice_ordinato = indice_ordinato + 1

while j_sublist_index < len(j_sublist):

lista1[indice_ordinato] = j_sottolista[j_sottolista_indice]

j_sublist_index = j_sublist_index + 1

indice_ordinato = indice_ordinato + 1

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

se io >= j:

Restituzione

k = (io + j)//2

merge_sort(lista1, i, k, comp_fun)

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

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

car1 = Auto(“Jeep”, “Wrangler”, 0.58)

car2 = Auto(“Ford”, “Endeavour”, 0.35)

car3 = Auto("Jaguar Land Rover", "Range Rover Sport", 1.76)

car4 = Auto(“Mercedes Benz”, “Classe G”, 2.42)

lista1 = [auto1, auto2, auto3, auto4]

merge_sort(list1, 0, len(list1) -1, lambda autoA, autoB: autoA.marca < autoB.marca)

stampa ("Automobili ordinate per marca:")

per auto inlista1:

stampa (auto)

stampa ()

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

stampa ("Automobili ordinate per prezzo:")

per auto inlista1:

stampa (auto)

Produzione:

Auto ordinate per marca:

Ford Endeavour

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedes Benz Classe G

Auto ordinate per prezzo:

Ford Endeavour

Jeep Wrangler

Jaguar Land Rover Range Rover

Mercedes Benz Classe G

Puoi apprendere aspetti sia teorici che pratici di Python con il certificato professionale di upGrad in Data Science e Business Analytics dell'Università del Maryland. Questo corso ti aiuta a imparare Python da zero. Anche se sei nuovo alla programmazione e alla codifica, upGrad ti offrirà un corso preparatorio di due settimane in modo che tu possa apprendere le basi della programmazione. imparerai a conoscere vari strumenti come Python, SQL, mentre lavori su più progetti di settore.

Pianifica ora la tua carriera nello sviluppo software!

Richiedi il programma di certificazione professionale in Data Science e Business Analytics