Sortarea prin îmbinare este similară cu algoritmul de sortare rapidă, deoarece funcționează pe conceptul de împărțire și cucerire. Este unul dintre cei mai populari și mai eficienti algoritmi de sortare. Este cel mai bun exemplu pentru categoria de algoritmi împărțiți și cuceriți.
Împarte lista dată în cele două jumătăți, se numește singur pentru cele două jumătăți și apoi îmbină cele două jumătăți sortate. Noi definim combina() funcție obișnuită să îmbine două jumătăți.
Sublistele sunt împărțite din nou și din nou în jumătăți până când obținem un singur element fiecare. Apoi combinăm perechea de liste cu un element în liste de două elemente, sortându-le în acest proces. Cele două perechi de elemente sortate sunt îmbinate în cele patru liste de elemente și așa mai departe până când obținem lista sortată.
Conceptul de sortare fuzionare
Să vedem următoarea diagramă de sortare Merge.
Am împărțit lista dată în două jumătăți. Lista nu poate fi împărțită în părți egale, nu contează deloc.
Sortarea prin îmbinare poate fi implementată folosind două moduri - abordare de sus în jos și abordare de jos în sus. Folosim abordarea de sus în jos în exemplul de mai sus, care este sortarea Merge cel mai des folosită.
Abordarea de jos în sus oferă mai multă optimizare pe care o vom defini mai târziu.
Partea principală a algoritmului este modul în care combinăm cele două subliste sortate. Să îmbinăm cele două liste de îmbinare sortate.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- sortat : gol
În primul rând, observăm primul element al ambelor liste. Găsim că primul element al lui B este mai mic, așa că îl adăugăm în lista noastră sortată și avansăm în lista B.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , unsprezece]
- Sortat: 1
Acum ne uităm la următoarea pereche de elemente 2 și 3. 2 este mai mic, așa că îl adăugăm în lista noastră sortată și trecem înainte la listă.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , unsprezece]
- Sortat: 1
Continuați acest proces și ajungem la lista sortată de {1, 2, 3, 4, 7, 8, 11}. Pot exista două cazuri speciale.
amestec omogen
Ce se întâmplă dacă ambele sub-liste au aceleași elemente - În acest caz, putem muta oricare sub-listă și putem adăuga elementul la lista sortată. Din punct de vedere tehnic, putem avansa în ambele subliste și putem adăuga elemente la lista sortată.
Nu avem niciun element rămas într-o singură sublistă. Când epuizăm într-o sub-listă pur și simplu adăugați elementul celui de-al doilea unul după altul.
Ar trebui să ne amintim că putem sorta elementul în orice ordine. Sortăm lista dată în ordine crescătoare, dar putem sorta cu ușurință în ordine descrescătoare.
Implementarea
Algoritmul de sortare de îmbinare este implementat folosind abordarea de sus în jos. Poate părea ușor dificil, așa că vom elabora detaliile fiecărui pas. Aici, vom implementa acest algoritm pe două tipuri de colecții - lista de elemente întregi (utilizată de obicei pentru a introduce sortarea) și un obiect personalizat (un scenariu mai practic și mai realist).
Sorting Array
Conceptul principal de algoritm este de a împărți (sub)lista în jumătăți și de a le sorta recursiv. Continuăm procesul până când ajungem la liste care au un singur element. Să înțelegem următoarea funcție pentru divizare -
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)
Obiectivul nostru principal este de a împărți lista în subpărți înainte de a avea loc sortarea. Trebuie să obținem valoarea întreagă, așa că folosim operatorul // pentru indicii noștri.
Să înțelegem procedura de mai sus urmând pașii.
- Primul pas este să creați copii ale listelor. Prima listă conține listele de la [index_stânga,...,mijloc] iar al doilea din [middle+1,?,right_index] .
- Parcurgem ambele copii ale listei folosind indicatorul, selectăm valoarea mai mică a celor două valori și le adăugăm la lista sortată. Odată ce adăugăm elementul în listă și mergem mai departe în lista sortată, indiferent.
- Adăugați elementele rămase în cealaltă copie la matricea sortată.
Să implementăm sortarea de îmbinare în programul Python.
Programul 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)> Sortarea obiectelor personalizate
De asemenea, putem sorta obiectele personalizate folosind Piton clasă. Acest algoritm este aproape similar cu cel de mai sus, dar trebuie să-l facem mai versatil și să trecem funcția de comparare.
Vom crea o clasă personalizată, Car și vom adăuga câteva câmpuri la ea. Facem câteva modificări în algoritmul de mai jos pentru a-l face mai versatil. Putem face acest lucru folosind funcțiile lambda.
Să înțelegem următorul exemplu.
Programul 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)> Optimizare
Putem îmbunătăți performanța algoritmului de sortare de îmbinare. Mai întâi să înțelegem diferența dintre sortarea îmbinării de sus în jos și de jos în sus. Abordarea de jos în sus sortează elementele listelor adiacente în mod iterativ, în cazul în care abordarea de sus în jos descompune listele în cele două jumătăți.
Lista dată este [10, 4, 2, 12, 1, 3], în loc să o împărțim în [10], [4], [2], [12], [1], [3] - împărțim în sublistele care pot fi deja sortate: [10, 4], [2], [1, 12], [3] și acum sunteți gata să le sortați.
Sortarea prin îmbinare este un algoritm ineficient atât în timp, cât și în spațiu pentru sublistele mai mici. Deci, sortarea prin inserare este un algoritm mai eficient decât sortarea prin îmbinare pentru sublistele mai mici.
Concluzie
Sortarea prin îmbinare este un algoritm popular și eficient. Este un algoritm mai eficient pentru listele mari. Nu depinde de deciziile nefericite care duc la timpi de execuție prost.
Există un demerit major în tipul de îmbinare. Utilizează memoria suplimentară care este utilizată pentru a stoca copiile temporare ale listelor înainte de a le îmbina. Cu toate acestea, sortarea Merge este utilizată pe scară largă în software. Performanța sa este rapidă și produce un rezultat excelent.
Am discutat pe scurt conceptul de sortare de îmbinare și am implementat-o atât pe o listă simplă de întregi, cât și pe obiecte personalizate printr-o funcție lambda utilizată pentru comparație.
parseint java