Zlúčiť triedenie je podobné rýchlemu triediacemu algoritmu, pretože funguje na koncepte rozdelenia a panovania. Je to jeden z najpopulárnejších a najúčinnejších triediacich algoritmov. Je to najlepší príklad pre kategóriu algoritmov rozdeľuj a panuj.

Rozdelí daný zoznam na dve polovice, zavolá sa na dve polovice a potom tieto dve zoradené polovice spojí. Definujeme zlúčiť() funkcia používaná na spojenie dvoch polovíc.

Podzoznamy sa znova a znova delia na polovice, až kým nedostaneme každý jediný prvok. Potom spojíme pár zoznamov jedného prvku do dvoch zoznamov prvkov, pričom ich v procese triedime. Zoradené dva páry prvkov sa zlúčia do štyroch zoznamov prvkov a tak ďalej, kým nezískame zoradený zoznam.

Koncept zoradenia zlúčením

Pozrime sa na nasledujúci diagram triedenia zlúčenia.

Uvedený zoznam sme rozdelili na dve polovice. Zoznam sa nedal rozdeliť na rovnaké časti, na tom vôbec nezáleží.

Zlúčiť triedenie je možné realizovať dvoma spôsobmi – prístupom zhora nadol a prístupom zdola nahor. Vo vyššie uvedenom príklade používame prístup zhora nadol, čo je najčastejšie používané triedenie zlučovania.

Prístup zdola nahor poskytuje väčšiu optimalizáciu, ktorú si zadefinujeme neskôr.

Hlavnou časťou algoritmu je to, ako kombinujeme dva zoradené podzoznamy. Poďme zlúčiť dva zoradené zoznamy zlúčenia.

• A: [ 2 , 4, 7, 8]
• B: [ 1 , 3, 11]
• zoradené : prázdne

Najprv sledujeme prvý prvok oboch zoznamov. Zistili sme, že prvý prvok B je menší, takže ho pridáme do nášho zoradeného zoznamu a posunieme sa vpred v zozname B.

• A: [ 2 , 4, 7, 8]
• B: [1, 3 , jedenásť]
• Zoradené: 1

Teraz sa pozrieme na ďalší pár prvkov 2 a 3. 2 je menší, takže ho pridáme do nášho zoradeného zoznamu a presunieme sa dopredu na zoznam.

• A: [ 2 , 4, 7, 8]
• B: [1, 3 , jedenásť]
• Zoradené: 1

Pokračujte v tomto procese a skončíme so zoradeným zoznamom {1, 2, 3, 4, 7, 8, 11}. Môžu nastať dva špeciálne prípady.

modem vs router

Čo ak majú oba podzoznamy rovnaké prvky - V takom prípade môžeme presunúť jeden podzoznam a pridať prvok do zoradeného zoznamu. Technicky sa môžeme posunúť vpred v oboch podzoznamoch a pridať prvky do zoradeného zoznamu.

V jednom podzozname už nemáme žiadny prvok. Keď vyčerpáme zoznam v podzozname, jednoducho pridajte prvok druhého prvku za druhým.

Mali by sme pamätať na to, že prvok môžeme triediť v ľubovoľnom poradí. Daný zoznam zoradíme vzostupne, ale môžeme ľahko zoradiť aj zostupne.

Implementácia

Algoritmus triedenia zlúčenia sa implementuje pomocou prístupu zhora nadol. Môže sa to zdať trochu zložité, preto podrobne rozvedieme každý krok. Tu implementujeme tento algoritmus na dva typy kolekcií – celočíselný zoznam prvkov (zvyčajne sa používa na zavedenie triedenia) a vlastný objekt (praktickejší a realistickejší scenár).

python znížiť

Pole triedenia

Hlavným konceptom algoritmu je rozdelenie (pod)zoznamu na polovice a ich rekurzívne triedenie. Pokračujeme v procese, kým neskončíme so zoznamami, ktoré majú iba jeden prvok. Poďme pochopiť nasledujúcu funkciu pre delenie -

 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) 

Naším hlavným cieľom je rozdeliť zoznam na podčasti predtým, ako dôjde k triedeniu. Potrebujeme získať celočíselnú hodnotu, takže pre naše indexy použijeme operátor //.

Poďme pochopiť vyššie uvedený postup pomocou nasledujúcich krokov.

• Prvým krokom je vytvorenie kópií zoznamov. Prvý zoznam obsahuje zoznamy z [ľavý_index,...,uprostred] a druhý z [middle+1,?,right_index] .
• Prechádzame oboma kópiami zoznamu pomocou ukazovateľa, vyberieme menšiu hodnotu z dvoch hodnôt a pridáme ich do zoradeného zoznamu. Po pridaní prvku do zoznamu sa bez ohľadu na to posúvame ďalej v zoradenom zozname.
• Pridajte zostávajúce prvky v druhej kópii do zoradeného poľa.

Implementujme zlučovacie triedenie v programe Python.

Program 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 &gt;= 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&apos;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(&apos;Make: {}, Model: {}, Year: {}&apos;, 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(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 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&apos;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)>

Triedenie vlastných objektov

Vlastné objekty môžeme triediť aj pomocou Python trieda. Tento algoritmus je takmer podobný vyššie uvedenému, ale musíme ho urobiť všestrannejším a prejsť funkciou porovnávania.

Vytvoríme vlastnú triedu Car a pridáme k nej niekoľko polí. V nižšie uvedenom algoritme robíme niekoľko zmien, aby bol všestrannejší. Môžeme to urobiť pomocou funkcií lambda.

Poďme pochopiť nasledujúci príklad.

Program 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(&apos;Make: {}, Model: {}, Year: {}&apos;, 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(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 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&apos;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)>

Optimalizácia

Môžeme zlepšiť výkon triediaceho algoritmu zlúčenia. Najprv pochopme rozdiel medzi zoradením zlúčenia zhora nadol a zdola nahor. Prístup zdola nahor triedi prvky susediacich zoznamov iteračne, pričom prístup zhora nadol rozdeľuje zoznamy na dve polovice.

Daný zoznam je [10, 4, 2, 12, 1, 3], namiesto toho, aby sme ho rozdelili na [10], [4], [2], [12], [1], [3] - delíme do podzoznamov, ktoré už môžu byť zoradené: [10, 4], [2], [1, 12], [3] a teraz sú pripravené na ich triedenie.

Zlúčiť triedenie je neefektívny algoritmus v čase aj priestore pre menšie podzoznamy. Takže triedenie vložením je efektívnejší algoritmus ako zlučovacie triedenie pre menšie podzoznamy.

Záver

Merge sort je populárny a efektívny algoritmus. Je to efektívnejší algoritmus pre veľké zoznamy. Nezáleží na žiadnych nešťastných rozhodnutiach, ktoré vedú k zlým prevádzkovým časom.

Zlučovanie má jednu veľkú nevýhodu. Používa dodatočnú pamäť, ktorá sa používa na ukladanie dočasných kópií zoznamov pred ich zlúčením. V softvéri sa však široko používa triedenie Merge. Jeho výkon je rýchly a prináša vynikajúci výsledok.

Stručne sme diskutovali o koncepte zoradenia zlúčenia a implementovali sme ho ako na jednoduchý celočíselný zoznam, tak aj na vlastné objekty prostredníctvom funkcie lambda používanej na porovnanie.