Razvrščanje z združitvijo je podobno algoritmu hitrega razvrščanja, saj deluje na konceptu deli in vladaj. Je eden najbolj priljubljenih in učinkovitih algoritmov za razvrščanje. Je najboljši primer za kategorijo algoritmov deli in vladaj.
Podani seznam razdeli na dve polovici, se pokliče za obe polovici in nato združi dve razvrščeni polovici. Definiramo združi () funkcija, ki se uporablja za združitev dveh polovic.
Podsezname vedno znova delimo na polovice, dokler ne dobimo enega samega elementa. Nato združimo par seznamov enega elementa v dva seznama elementov in ju pri tem razvrstimo. Razvrščena dva para elementov se združita v štiri sezname elementov in tako naprej, dokler ne dobimo razvrščenega seznama.
Koncept razvrščanja z združevanjem
Oglejmo si naslednji diagram razvrščanja z združevanjem.
Dani seznam smo razdelili na dve polovici. Seznama ni mogoče razdeliti na enake dele, to sploh ni pomembno.
Razvrščanje z združitvijo je mogoče izvesti na dva načina - pristop od zgoraj navzdol in pristop od spodaj navzgor. V zgornjem primeru uporabljamo pristop od zgoraj navzdol, ki je najpogosteje uporabljeno razvrščanje z združevanjem.
Pristop od spodaj navzgor zagotavlja večjo optimizacijo, ki jo bomo definirali kasneje.
Glavni del algoritma je, kako združimo dva razvrščena podseznama. Spojimo dva razvrščena spojena seznama.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- razvrščeno : prazno
Najprej opazujemo prvi element obeh seznamov. Ugotovimo, da je prvi element B manjši, zato ga dodamo na naš razvrščeni seznam in se premaknemo naprej na seznamu B.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , enajst]
- Razvrščeno: 1
Zdaj si ogledamo naslednji par elementov 2 in 3. 2 je manjši, zato ga dodamo na naš razvrščeni seznam in se premaknemo naprej na seznam.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , enajst]
- Razvrščeno: 1
Nadaljujte s tem postopkom in na koncu bomo imeli razvrščen seznam {1, 2, 3, 4, 7, 8, 11}. Lahko sta dva posebna primera.
fibonaccijeva vrsta v c
Kaj pa, če imata oba podseznama enake elemente - V tem primeru lahko premaknemo enega od podseznamov in dodamo element na razvrščen seznam. Tehnično se lahko premaknemo naprej na obeh podseznamih in dodamo elemente na razvrščeni seznam.
Na enem podseznamu nimamo več nobenega elementa. Ko nam zmanjka na podseznamu preprosto dodamo element drugega enega za drugim.
Ne smemo pozabiti, da lahko elemente razvrstimo v poljubnem vrstnem redu. Podan seznam razvrstimo v naraščajočem vrstnem redu, vendar ga lahko enostavno razvrstimo v padajočem vrstnem redu.
Izvedba
Algoritem razvrščanja z združitvijo je implementiran s pristopom od zgoraj navzdol. Morda je videti nekoliko težko, zato bomo podrobneje opisali vsak korak. Tu bomo implementirali ta algoritem na dve vrsti zbirk – seznam celih elementov (ki se običajno uporablja za uvedbo razvrščanja) in objekt po meri (bolj praktičen in realističen scenarij).
Razvrščanje niza
Glavni koncept algoritma je razdeliti (pod)seznam na polovice in jih rekurzivno razvrstiti. Postopek nadaljujemo, dokler ne dobimo seznamov, ki imajo samo en element. Razumejmo naslednjo funkcijo za deljenje -
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š glavni cilj je razdeliti seznam na poddele, preden pride do razvrščanja. Dobiti moramo celoštevilsko vrednost, zato za naše indekse uporabimo operator //.
Razumejmo zgornji postopek z naslednjimi koraki.
- Prvi korak je ustvariti kopije seznamov. Prvi seznam vsebuje sezname iz [levo_indeks,...,sredina] in drugi od [sredina+1,?,desno_indeks] .
- S kazalcem prečkamo obe kopiji seznama, izberemo manjšo vrednost obeh vrednosti in ju dodamo na razvrščen seznam. Ko dodamo element na seznam, se ne glede na to premaknemo naprej na razvrščenem seznamu.
- Dodajte preostale elemente v drugi kopiji v razvrščeni niz.
Implementirajmo razvrščanje z zlivanjem v programu Python.
js zamenjava
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 >= 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)> Razvrščanje predmetov po meri
Objekte po meri lahko razvrstimo tudi z uporabo Python razred. Ta algoritem je skoraj podoben zgornjemu, vendar ga moramo narediti bolj vsestranskega in prenesti primerjalno funkcijo.
Ustvarili bomo razred po meri Car in mu dodali nekaj polj. V spodnji algoritem naredimo nekaj sprememb, da bo bolj vsestranski. To lahko naredimo z uporabo lambda funkcij.
Razumejmo naslednji primer.
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('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)> Optimizacija
Izboljšamo lahko delovanje algoritma razvrščanja z združevanjem. Najprej poglejmo razliko med razvrščanjem spajanja od zgoraj navzdol in od spodaj navzgor. Pristop od spodaj navzgor razvršča elemente sosednjih seznamov iterativno, medtem ko pristop od zgoraj navzdol razdeli sezname na dve polovici.
Podani seznam je [10, 4, 2, 12, 1, 3], namesto da bi ga razdelili na [10], [4], [2], [12], [1], [3] - delimo v podsezname, ki so morda že razvrščeni: [10, 4], [2], [1, 12], [3] in so zdaj pripravljeni, da jih razvrstite.
Razvrščanje z združevanjem je neučinkovit algoritem tako v času kot v prostoru za manjše podsezname. Torej je razvrščanje z vstavljanjem učinkovitejši algoritem kot razvrščanje z združevanjem za manjše podsezname.
Zaključek
Razvrščanje z združitvijo je priljubljen in učinkovit algoritem. Je učinkovitejši algoritem za velike sezname. Ni odvisno od kakršnih koli nesrečnih odločitev, ki vodijo v slabo delovanje.
Pri razvrščanju z združitvijo je ena velika pomanjkljivost. Uporablja dodatni pomnilnik, ki se uporablja za shranjevanje začasnih kopij seznamov, preden jih združi. Vendar se v programski opremi pogosto uporablja razvrščanje z združevanjem. Njegovo delovanje je hitro in daje odlične rezultate.
Na kratko smo razpravljali o konceptu razvrščanja z združitvijo in ga implementirali tako na seznam preprostih celih števil kot tudi na objekte po meri prek funkcije lambda, ki se uporablja za primerjavo.