Sujungimo rūšiavimas yra panašus į greitojo rūšiavimo algoritmą, nes veikia su padalijimo ir užkariauk koncepcija. Tai vienas populiariausių ir efektyviausių rūšiavimo algoritmų. Tai geriausias algoritmų kategorijos „skaldyk ir valdyk“ pavyzdys.
Jis padalija pateiktą sąrašą į dvi dalis, vadinasi dviem pusėms ir sujungia dvi surūšiuotas dalis. Mes apibrėžiame sujungti () funkcija, naudojama sujungti dvi dalis.
Antriniai sąrašai vėl ir vėl dalijami į pusę, kol gauname po vieną elementą. Tada sujungiame vieno elemento sąrašų porą į du elementų sąrašus, rūšiuodami juos proceso metu. Surūšiuotos dvi elementų poros sujungiamos į keturis elementų sąrašus ir taip toliau, kol gauname surūšiuotą sąrašą.
Sujungti rūšiavimo koncepciją
Pažiūrėkime šią sujungimo rūšiavimo diagramą.
Pateiktą sąrašą padalinome į dvi dalis. Sąrašo negalima padalyti į lygias dalis, tai visiškai nesvarbu.
Sujungti rūšiavimą galima dviem būdais – metodu „iš viršaus į apačią“ ir „iš apačios į viršų“. Aukščiau pateiktame pavyzdyje naudojame metodą iš viršaus į apačią, kuris dažniausiai naudojamas Rūšiuoti sujungti.
„Iš apačios į viršų“ metodas suteikia daugiau optimizavimo, kurį apibūdinsime vėliau.
Pagrindinė algoritmo dalis yra ta, kaip mes sujungiame du surūšiuotus posąraščius. Sujungkime du surūšiuotus sujungimo sąrašus.
- A: [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- surūšiuota: tuščia
Pirmiausia stebime pirmąjį abiejų sąrašų elementą. Pastebime, kad pirmasis B elementas yra mažesnis, todėl įtraukiame jį į surūšiuotą sąrašą ir einame į priekį B sąraše.
- A: [ 2 , 4, 7, 8]
- B : [1, 3 , vienuolika]
- Rūšiuota: 1
Dabar žiūrime į kitą 2 ir 3 elementų porą. 2 yra mažesnė, todėl įtraukiame jį į surūšiuotą sąrašą ir pereiname prie sąrašo.
- A: [ 2 , 4, 7, 8]
- B : [1, 3 , vienuolika]
- Rūšiuota: 1
Tęskite šį procesą ir gausime surūšiuotą sąrašą {1, 2, 3, 4, 7, 8, 11}. Gali būti du ypatingi atvejai.
programėlė programėlė
Ką daryti, jei abu antriniai sąrašai turi tuos pačius elementus – Tokiu atveju galime perkelti bet kurį posarašį ir įtraukti elementą į surūšiuotą sąrašą. Techniškai galime judėti pirmyn abiejuose antriniuose sąrašuose ir įtraukti elementus į surūšiuotą sąrašą.
Viename antriniame sąraše nebeliko elementų. Kai pasibaigia antrinis sąrašas, tiesiog pridėkite antrojo elementą po kito.
Turėtume prisiminti, kad elementą galime rūšiuoti bet kokia tvarka. Pateiktą sąrašą rūšiuojame didėjančia tvarka, bet galime lengvai rūšiuoti mažėjančia tvarka.
Įgyvendinimas
Sujungimo rūšiavimo algoritmas įgyvendinamas naudojant metodą „iš viršaus į apačią“. Tai gali atrodyti šiek tiek sudėtinga, todėl mes pateiksime išsamią informaciją apie kiekvieną žingsnį. Čia mes įgyvendinsime šį algoritmą dviejų tipų kolekcijose – sveikųjų skaičių elementų sąraše (paprastai naudojamas rūšiavimui įvesti) ir pasirinktiniam objektui (praktiškesnis ir tikroviškesnis scenarijus).
Rūšiavimo masyvas
Pagrindinė algoritmo samprata yra padalyti (sub)sąrašą į pusę ir surūšiuoti juos rekursyviai. Tęsiame procesą, kol baigiame sąrašus, kuriuose yra tik vienas elementas. Supraskime šią padalijimo funkciją -
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)
Prieš rūšiavimą pirmiausia stengiamės suskirstyti sąrašą į poskyrius. Turime gauti sveikojo skaičiaus reikšmę, kad savo indeksams naudotume operatorių //.
Supraskime aukščiau aprašytą procedūrą atlikdami šiuos veiksmus.
- Pirmasis žingsnis yra sukurti sąrašų kopijas. Pirmame sąraše yra sąrašai iš [left_index,...,middle] o antrasis iš [vidurinis +1,?,dešinysis_indeksas] .
- Mes perkeliame abi sąrašo kopijas naudodami žymeklį, pasirenkame mažesnę dviejų reikšmių reikšmę ir įtraukiame jas į surūšiuotą sąrašą. Pridėję elementą į sąrašą ir rūšiuotame sąraše judame į priekį, nepaisant to.
- Į surūšiuotą masyvą pridėkite likusius elementus kitoje kopijoje.
Įdiegsime sujungimo rūšiavimą Python programoje.
Python programa
# 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)> Pasirinktinių objektų rūšiavimas
Taip pat galime rūšiuoti pasirinktinius objektus naudodami Python klasė. Šis algoritmas yra beveik panašus į aukščiau pateiktą, tačiau turime padaryti jį universalesnį ir perduoti palyginimo funkciją.
Sukursime pasirinktinę klasę Automobilis ir pridėsime prie jos keletą laukelių. Toliau pateiktame algoritme atliekame keletą pakeitimų, kad jis būtų universalesnis. Tai galime padaryti naudodami lambda funkcijas.
Supraskime šį pavyzdį.
Python programa
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)> Optimizavimas
Galime pagerinti sujungimo rūšiavimo algoritmo našumą. Pirmiausia supraskime skirtumą tarp rūšiavimo iš viršaus į apačią ir iš apačios į viršų. Taikant metodą „iš apačios į viršų“, gretimų sąrašų elementai rūšiuojami kartotiškai, kai metodas „iš viršaus į apačią“ suskaido sąrašus į dvi dalis.
Pateiktas sąrašas yra [10, 4, 2, 12, 1, 3], užuot suskirstę jį į [10], [4], [2], [12], [1], [3] – padaliname į antrinius sąrašus, kurie jau gali būti surūšiuoti: [10, 4], [2], [1, 12], [3] ir dabar yra pasirengę juos rūšiuoti.
Sujungimo rūšiavimas yra neefektyvus algoritmas tiek laiko, tiek erdvės atžvilgiu mažesniems antriniams sąrašams. Taigi, įterpimo rūšiavimas yra efektyvesnis algoritmas nei mažesnių antrinių sąrašų sujungimo rūšiavimas.
dar java
Išvada
Sujungimo rūšiavimas yra populiarus ir efektyvus algoritmas. Tai efektyvesnis algoritmas dideliems sąrašams. Tai nepriklauso nuo bet kokių nesėkmingų sprendimų, dėl kurių blogai veikia.
Yra vienas didelis sujungimo trūkumas. Jis naudoja papildomą atmintį, kuri naudojama laikinoms sąrašų kopijoms saugoti prieš juos sujungiant. Tačiau programinėje įrangoje plačiai naudojamas sujungimo rūšiavimas. Jo veikimas yra greitas ir duoda puikų rezultatą.
Trumpai aptarėme sujungimo rūšiavimo koncepciją ir įdiegėme ją tiek paprastame sveikųjų skaičių sąraše, tiek pasirinktiniuose objektuose naudodami lambda funkciją, naudojamą palyginimui.