Slå sammen sortering ligner på hurtigsorteringsalgoritmen som arbeider med konseptet del og hersk. Det er en av de mest populære og effektive sorteringsalgoritmene. Det er det beste eksemplet for dele og hersk kategori av algoritmer.

Den deler den gitte listen i de to halvdelene, kaller seg selv for de to halvdelene og slår deretter sammen de to sorterte halvdelene. Vi definerer slå sammen() funksjon som brukes til å slå sammen to halvdeler.

Underlistene deles gang på gang i halvdeler til vi får det eneste elementet hver. Deretter kombinerer vi paret med ett elementlister til to elementlister, og sorterer dem i prosessen. De sorterte to elementparene slås sammen til de fire elementlistene, og så videre til vi får den sorterte listen.

Slå sammen sorteringskonsept

La oss se følgende sorteringsdiagram for sammenslåing.

Vi har delt den gitte listen i de to halvdelene. Listen kunne ikke deles i like deler, det spiller ingen rolle i det hele tatt.

Sammenslåingssortering kan implementeres ved å bruke to måter - top-down-tilnærming og bottom-up-tilnærming. Vi bruker ovenfra og ned-tilnærmingen i eksemplet ovenfor, som er Merge sort som oftest brukes.

Bottom-up-tilnærmingen gir mer optimalisering som vi vil definere senere.

Hoveddelen av algoritmen er hvordan vi kombinerer de to sorterte underlistene. La oss slå sammen den to-sorterte flettelisten.

• A: [ 2 , 4, 7, 8]
• B : [ 1 , 3, 11]
• sortert : tom

Først observerer vi det første elementet i begge listene. Vi finner at Bs første element er mindre, så vi legger dette til i vår sorterte liste og går videre i B-listen.

• A: [ 2 , 4, 7, 8]
• B: [1, 3 , elleve]
• Sortert: 1

Nå ser vi på neste par av elementer 2 og 3. 2 er mindre, så vi legger det til i vår sorterte liste og går videre til listen.

• A: [ 2 , 4, 7, 8]
• B: [1, 3 , elleve]
• Sortert: 1

Fortsett denne prosessen og vi ender opp med den sorterte listen med {1, 2, 3, 4, 7, 8, 11}. Det kan være to spesielle tilfeller.

Java swing opplæring

Hva om begge underlistene har samme elementer - I slike tilfeller kan vi flytte en av underlistene og legge til elementet i den sorterte listen. Teknisk sett kan vi gå videre i både underlisten og legge til elementene til den sorterte listen.

Vi har ingen elementer igjen i én underliste. Når vi går tom for i en underliste, legger du bare til elementet i den andre etter hverandre.

Vi bør huske at vi kan sortere elementet i hvilken som helst rekkefølge. Vi sorterer den gitte listen i stigende rekkefølge, men vi kan enkelt sortere i synkende rekkefølge.

Gjennomføring

Algoritmen for sammenslåingssortering implementeres ved å bruke ovenfra-ned-tilnærmingen. Det kan se litt vanskelig ut, så vi vil utdype hver step-in detalj. Her vil vi implementere denne algoritmen på to typer samlinger - heltallselementliste (vanligvis brukt til å introdusere sortering) og et tilpasset objekt (et mer praktisk og realistisk scenario).

Sorteringsarray

Hovedkonseptet med algoritme er å dele (under)liste i halvdeler og sortere dem rekursivt. Vi fortsetter prosessen til vi ender opp med lister som kun har ett element. La oss forstå følgende funksjon for divisjon -

 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) 

Vårt primære fokus er å dele listen inn i underdeler før sorteringen skjer. Vi må få heltallsverdien, så vi bruker //-operatoren for indeksene våre.

La oss forstå prosedyren ovenfor ved å følge trinnene.

• Første trinn er å lage kopier av lister. Den første listen inneholder listene fra [venstre_indeks,...,midt] og den andre fra [midt+1,?,høyre_indeks] .
• Vi krysser begge kopiene av listen ved å bruke pekeren, velger den minste verdien av de to verdiene og legger dem til den sorterte listen. Når vi legger til elementet i listen, og vi beveger oss fremover i den sorterte listen uansett.
• Legg til de resterende elementene i den andre kopien til den sorterte matrisen.

La oss implementere flettesorteringen i Python-programmet.

Python-programmet

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

Sortering av egendefinerte objekter

Vi kan også sortere de tilpassede objektene ved å bruke Python klasse. Denne algoritmen er nesten lik den ovenfor, men vi må gjøre den mer allsidig og bestå sammenligningsfunksjonen.

Vi vil lage en tilpasset klasse, Bil og legge til noen få felt til den. Vi gjør noen få endringer i algoritmen nedenfor for å gjøre den mer allsidig. Dette kan vi gjøre ved å bruke lambda-funksjonene.

fjær mvc

La oss forstå følgende eksempel.

Python-programmet

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

Optimalisering

Vi kan forbedre ytelsen til sammenslåingssorteringsalgoritmen. La oss først forstå forskjellen mellom sammenslåingssortering ovenfra og ned og nedenfra og opp. Nedenfra-og-opp-tilnærmingen sorterer elementene i tilstøtende lister iterativt, der ovenfra-og-ned-tilnærmingen bryter ned listene i to halvdeler.

Den gitte listen er [10, 4, 2, 12, 1, 3], i stedet for å dele den opp i [10], [4], [2], [12], [1], [3] - vi deler opp inn i underlistene som kanskje allerede er sortert: [10, 4], [2], [1, 12], [3] og er nå klare til å sortere dem.

Slå sammen sortering er ineffektiv algoritme både i tid og rom for de mindre underlistene. Så innsettingssortering er en mer effektiv algoritme enn sammenslåingssortering for de mindre underlistene.

Konklusjon

Merge sort er en populær og effektiv algoritme. Det er en mer effektiv algoritme for de store listene. Det er ikke avhengig av eventuelle uheldige avgjørelser som fører til dårlige kjøretider.

Det er én stor ulempe ved sammenslåingen. Den bruker det ekstra minnet som brukes til å lagre de midlertidige kopiene av lister før de slås sammen. Merge sort er imidlertid mye brukt i programvaren. Ytelsen er rask og gir et utmerket resultat.

Vi har diskutert sammenslåingssortering-konseptet i korthet og implementert det både på enkel heltallsliste og på tilpassede objekter via en lambda-funksjon som brukes til sammenligning.