TechCodeview

Az összevonási rendezés hasonló a gyors rendezési algoritmushoz, mivel az oszd meg és uralkodj koncepción dolgozik. Ez az egyik legnépszerűbb és leghatékonyabb rendezési algoritmus. Ez a legjobb példa az oszd meg és uralkodj kategóriájú algoritmusokra.

Az adott listát két felére osztja, a két félnek felhívja magát, majd összevonja a két rendezett felét. Meghatározzuk a összeolvad() két fél egyesítésére használt funkció.

Az allistákat újra és újra felezzük, amíg meg nem kapjuk az egyetlen elemet. Ezután az egy elem listák párját összevonjuk két elemlistává, és közben rendezzük őket. A rendezett két elempár összevonódik a négy elemlistába, és így tovább, amíg meg nem kapjuk a rendezett listát.

Összevonási rendezési koncepció

Lássuk a következő összevonási rendezési diagramot.

A megadott listát két részre osztottuk. A listát nem lehetett egyenlő részekre osztani, ez teljesen mindegy.

Az összevonási rendezés kétféle módon valósítható meg - felülről lefelé és alulról felfelé. A fenti példában a felülről lefelé irányuló megközelítést használjuk, amely a leggyakrabban használt összevonási rendezés.

Az alulról felfelé irányuló megközelítés nagyobb optimalizálást tesz lehetővé, amelyet később fogunk meghatározni.

Az algoritmus fő része az, hogy hogyan kombináljuk a két rendezett allistát. Egyesítsük a két rendezett egyesítési listát.

• A: [ 2 , 4, 7, 8]
• B : [ 1 , 3, 11]
• rendezve: üres

Először mindkét lista első elemét figyeljük meg. Úgy találjuk, hogy a B első eleme kisebb, ezért ezt hozzáadjuk a rendezett listánkhoz, és továbblépünk a B listán.

• A: [ 2 , 4, 7, 8]
• B : [1, 3 , tizenegy]
• Rendezés: 1

Most nézzük a következő 2-es és 3-as elempárt. A 2 kisebb, ezért hozzáadjuk a rendezett listánkhoz, és továbblépünk a listára.

• A: [ 2 , 4, 7, 8]
• B : [1, 3 , tizenegy]
• Rendezés: 1

Folytassa ezt a folyamatot, és a végén az {1, 2, 3, 4, 7, 8, 11} rendezett listát kapjuk. Két speciális eset lehet.

char és int java

Mi a teendő, ha mindkét allistának ugyanazok az elemei vannak - Ilyen esetben bármelyik allistát áthelyezhetjük, és hozzáadhatjuk az elemet a rendezett listához. Technikailag mindkét allistában előreléphetünk, és hozzáadhatjuk az elemeket a rendezett listához.

Egyetlen allistán sem maradt elemünk. Amikor elfogy az in a sub list, egyszerűen adja hozzá a második elemet egymás után.

Ne felejtsük el, hogy az elemeket tetszőleges sorrendbe rendezhetjük. Az adott listát növekvő sorrendbe rendezzük, de egyszerűen csökkenő sorrendbe rendezhetjük.

Végrehajtás

Az összevonási rendezési algoritmus felülről lefelé irányuló megközelítéssel valósul meg. Ez kissé bonyolultnak tűnhet, ezért minden egyes lépést részletesen kidolgozunk. Itt ezt az algoritmust kétféle gyűjteményre valósítjuk meg – egész szám elemlistán (általában a rendezés bevezetésére használják) és egy egyéni objektumon (praktikusabb és valósághűbb forgatókönyv).

Sorting Array

Az algoritmus fő koncepciója az (al)lista felezése és rekurzív rendezése. Addig folytatjuk a folyamatot, amíg olyan listákat nem kapunk, amelyeknek csak egy eleme van. Értsük meg a következő osztási függvényt -

 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) 

Elsődleges célunk, hogy a listát alrészekre osszuk a rendezés előtt. Meg kell kapnunk az egész értéket, így a // operátort használjuk indexeinkhez.

Értsük meg a fenti eljárást a következő lépésekkel.

• Az első lépés a listák másolatainak létrehozása. Az első lista a listákat tartalmazza [bal_index,...,közép] a második pedig abból [közép+1,?,jobb_index] .
• A mutató segítségével bejárjuk a lista mindkét példányát, kiválasztjuk a két érték közül a kisebb értéket és hozzáadjuk a rendezett listához. Miután hozzáadtuk az elemet a listához, ettől függetlenül haladunk előre a rendezett listában.
• Adja hozzá a másik példány többi elemét a rendezett tömbhöz.

Valósítsuk meg az összevonási rendezést a Python programban.

Python program

 # 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)>

Egyéni objektumok rendezése

Az egyéni objektumokat a segítségével is rendezhetjük Piton osztály. Ez az algoritmus majdnem hasonló a fentihez, de sokoldalúbbá kell tenni, és át kell adni az összehasonlító függvényt.

Létrehozunk egy egyéni osztályt, az Autót, és hozzáadunk néhány mezőt. Néhány változtatást végzünk az alábbi algoritmuson, hogy sokoldalúbbá tegyük. Ezt a lambda függvényekkel tehetjük meg.

Értsük meg a következő példát.

Python program

 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álás

Javíthatjuk az összevonási rendezési algoritmus teljesítményét. Először is értsük meg a különbséget a felülről lefelé és az alulról felfelé történő egyesítés rendezése között. Az alulról felfelé irányuló megközelítés iteratív módon rendezi a szomszédos listák elemeit, ahol a felülről lefelé irányuló megközelítés két részre bontja a listákat.

java string concat

A megadott lista: [10, 4, 2, 12, 1, 3], ahelyett, hogy felosztanánk [10], [4], [2], [12], [1], [3] -ra - osztjuk az allistákba, amelyek már rendezve: [10, 4], [2], [1, 12], [3], és készen állnak a rendezésre.

Az összevonási rendezés nem hatékony algoritmus mind időben, mind térben a kisebb allisták esetében. Tehát a beillesztési rendezés hatékonyabb algoritmus, mint a kisebb allisták összevonása.

Következtetés

Az összevonási rendezés népszerű és hatékony algoritmus. Hatékonyabb algoritmus a nagy listákhoz. Ez nem a szerencsétlen döntéseken múlik, amelyek rossz futásidőhöz vezetnek.

Az összevonásnak van egy nagy hátránya. Azt a kiegészítő memóriát használja, amely a listák ideiglenes másolatainak tárolására szolgál, mielőtt összevonná azokat. A Merge rendezést azonban széles körben használják a szoftverben. Teljesítménye gyors és kiváló eredményt produkál.

Röviden tárgyaltuk az összevonási rendezési koncepciót, és mind egyszerű egész listán, mind egyéni objektumokon implementáltuk az összehasonlításhoz használt lambda függvényen keresztül.