Programul Python pentru sortare prin îmbinare

Fiind un limbaj de programare cu mai multe paradigme, cu o abordare de proiectare structurată, orientată pe obiecte și sintaxă și gramatică simple și neaglomerate, Python devine rapid ca limbajul de alegere pentru programatorii care lucrează la proiecte de complexitate și scară variate.

Python oferă o bibliotecă modulară de algoritmi pre-construiți, care le permite utilizatorilor săi să efectueze diverse operațiuni care îi pot ajuta să-și îndeplinească sarcina în sine sau să servească ca un pas pe calea atingerii unui obiectiv mai mare și mai complex. Unul dintre cei mai populari astfel de algoritmi este unul care permite funcționalitatea Merge Sort.

Ce este Merge Sort?

Este o tehnică de sortare de uz general, care permite utilizatorilor să ia un set de date aleatoriu de orice tip și din orice sursă și să-l împartă în etape repetitive până când, în cele din urmă, este defalcat în componentele sale individuale - o tehnică recursivă, denumită în mod obișnuit „ metoda împărțiți și cuceriți.

Algoritmul reunește apoi componentele individuale – din nou în etape repetitive – dar le sortează într-o secvență logică prestabilită la fiecare etapă de-a lungul drumului, folosind comparația de bază și schimbarea până când întreaga serie de date este reconstituită în secvența logică dorită. .

Consultați celelalte cursuri ale noastre de știință a datelor la upGrad.

Tehnica Divide and Conquer

Luați, de exemplu, un set de date aleatoriu de litere ale alfabetului: N, H, V, B, Q, D, Z, R.

Pasul 1 : Setul de date original este mai întâi împărțit în două grupuri, după cum urmează:

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

Pasul 2 : Ambele matrice rezultate sunt subdivizate în continuare după cum urmează:

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

Pasul 3 : În cele din urmă, toate cele patru matrice sunt în continuare scuipat până când întreaga serie de date este împărțită în componentele sale individuale:

N H V B Q D Z R

Procesul se inversează, iar punctele de date individuale încep acum să se îmbine într-o manieră în etape. Dar pe parcursul acestui proces de fuziune, fiecare element din fiecare sub-matrice este evaluat și schimbat, astfel încât să se ordoneze într-o secvență logică (ordine alfabetică), după cum urmează:

Pasul 4 : elementele individuale se îmbină în perechi în timp ce schimbă pozițiile după cum este necesar pentru a forma secvența corectă:

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

Pasul 5 : Procesul recursiv de îmbinare și sortare continuă la următoarea iterație:

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

Pasul 6 : Întreaga serie de date este în cele din urmă reconstituită în ordinea sa logică alfabetică:

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

Explorați cursurile noastre populare de știință a datelor

Implementări de sortare îmbinate

Există două abordări pentru implementarea Merge Sort în Python. Abordarea de sus în jos și abordarea de jos în sus.

Abordare de sus în jos:

Abordarea de sus în jos mai des folosită este cea descrisă mai sus. Durează mai mult și consumă mai multă memorie și, prin urmare, este ineficient atunci când lucrați cu seturi de date mai mici. Cu toate acestea, este mult mai fiabil, în special atunci când este aplicat la seturi de date mari.

Citiți articolele noastre populare despre știința datelor

Cod de intrare:

def merge_sort (inp_arr):

dimensiune = len(inp_arr)

dacă dimensiunea > 1:

mijloc = dimensiune // 2

left_arr = inp_arr(:middle)

dreapta_arr = inp_arr(mijloc:)

merge_sort(left_arr)

merge _sort(right_arr)

i = 0

j = 0

k = 0

(Unde i și j sunt iteratorii pentru parcurgerea jumătăților din stânga și din dreapta ale seriei de date, respectiv, și k este iteratorul seriei totale de date).

dimensiune_stânga = len(arr_stânga)

right _size = len(right_arr)

în timp ce i < mărimea_stânga și j < dimensiunea dreaptă:

dacă stânga_arr(i) < right_arr (j):

inp_arr(k) – left_arr(i)

eu >= 1

altceva:

inp_arr(k) = right_arr (j)

j += 1

k += 1

în timp ce i < left_size:

inp_arr (k) = left_arr(i)

i += 1

k += 1

în timp ce j < mărimea_dreapta:

inp_arr (k) = right_arr(j)

j += 1

k += 1

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

print(:Input Array:\n”)

print(inp_arr)

merge_sort (inp_arr)

print(„Matrice sortată:\n”)

imprimare (inp_arr)

Ieșire:

Matrice de intrare: N, H, V, B, Q, D, Z, R

Matrice de ieșire: B, D, H, N, Q, R, V, Z

Abordarea de jos în sus:

Abordarea de jos în sus este mai rapidă, utilizează mai puțină memorie și funcționează eficient cu seturi de date mai mici, dar poate întâmpina probleme atunci când lucrați cu seturi de date mari. Prin urmare, este utilizat mai rar.

Cod de intrare:

def merge(stânga, dreapta):

rezultat = [] x, y = 0, 0

pentru k în interval (0, len(stânga) + len(dreapta)):

if i == len(stânga): # dacă la sfârșitul primei reprize,

result.append(right[j]) # adaugă toate valorile din a doua jumătate

j += 1

elif j == len(dreapta): # dacă la sfârșitul celei de-a doua jumătăți,

result.append(left[x]) # adaugă toate valorile din prima jumătate

i += 1

elif dreapta[j] < stânga[i]:

result.append(dreapta[j])

j += 1

altceva:

rezultat.append(stânga[i])

i += 1

returnează rezultatul

def mergesort(ar_list):

lungime = len(ar_list)

dimensiune = 1

în timp ce dimensiunea < lungime:

size+=size # se inițializează la 2 așa cum este descris

pentru poziție în interval (0, lungime, dimensiune):

start = poz

mid = pos + int (dimensiune / 2)

sfârşit = poz + mărime

stânga = lista_ar[ începutul: mijlocul] dreapta = lista_ar[ mijlocul: sfârşitul]

ar_list[start:end] = îmbinare(stânga, dreapta)

returnează ar_list

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

Ieșire:

Matrice de intrare: N, H, V, B, Q, D, Z, R

Matrice de ieșire: B, D, H, N, Q, R, V, Z

Implementarea Merge Sort aplicată la seturi de date mai complexe, din viața reală

Să aplicăm abordarea de sus în jos la patru vehicule de teren aleatorii din India:

Cod de intrare:

masina de clasa :

def __init__(self, brand, model, price):

self.brand = brand

self.model = model

self.price = pret

def __str__(self):

return str.format(„Brand: {}, Model: {}, Pret: {}”, self.brand,

auto.model, auto.pret)

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

stânga_copie = list1[i:k + 1]

r_sublist = list1[k+1:r+1]

index_copie_stânga = 0

j_sublist_index = 0

index_sortat = i

în timp ce left_copy_index < len(left_copy) șij_sublist_index <

len(j_sublist):

dacă comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = copie_stânga[index_copie_stânga]

index_copie_stânga = index_copie_stânga + 1

altceva :

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

index_sortat = index_sortat + 1

în timp ce left_copy_index < len(left_copy):

list1[sorted_index] = copie_stânga[index_copie_stânga]

index_copie_stânga = index_copie_stânga + 1

index_sortat = index_sortat + 1

în timp ce j_sublist_index < len(j_sublist):

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

index_sortat = index_sortat + 1

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

dacă i >= j:

întoarcere

k = (i + j)//2

merge_sort(list1, i, k, comp_fun)

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

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

mașină1 = Mașină ("Jeep", "Wrangler", 0,58)

mașină2 = Mașină(„Ford”, „Endeavour”, 0,35)

mașină3 = Mașină(„Jaguar Land Rover”, „Range Rover Sport”, 1.76)

mașină4 = Mașină(„Mercedes Benz”, „Clasa G”, 2.42)

list1 = [mașină1, mașină2, mașină3, mașină4]

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

print („Mașini sortate după marcă:”)

pentru mașina dinlista 1:

imprimare (masina)

imprimare ()

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

print („Mașini sortate după preț:”)

pentru mașina dinlista 1:

imprimare (masina)

Ieșire:

Mașini sortate după marcă:

Ford Endeavour

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedes Benz Clasa G

Mașini sortate după preț:

Ford Endeavour

Jeep Wrangler

Jaguar Land Rover Range Rover

Mercedes Benz Clasa G

Puteți învăța atât aspectele teoretice, cât și cele practice ale Python cu certificatul profesional upGrad în știința datelor și analiză de afaceri de la Universitatea din Maryland. Acest curs vă ajută să învățați Python de la zero. Chiar dacă sunteți nou în programare și codare, upGrad vă va oferi un curs pregătitor de două săptămâni, astfel încât să puteți învăța elementele de bază ale programării. veți afla despre diverse instrumente precum Python, SQL, în timp ce lucrați la mai multe proiecte din industrie.

Planifică-ți acum cariera de dezvoltare software!

Aplicați pentru programul de certificat profesional în știința datelor și analiză de afaceri