Merge sort ligner den hurtige sorteringsalgoritme, da den arbejder på begrebet del og hersk. Det er en af de mest populære og effektive sorteringsalgoritmer. Det er det bedste eksempel på opdel og hersk kategori af algoritmer.
Den deler den givne liste i de to halvdele, kalder sig selv for de to halvdele og slår derefter de to sorterede halvdele sammen. Vi definerer fusionere() funktion, der bruges til at slå to halvdele sammen.
Underlisterne opdeles igen og igen i halvdele, indtil vi får det eneste element hver. Derefter kombinerer vi parret af et element lister til to element lister, sorterer dem i processen. De sorterede to elementpar flettes ind i de fire elementlister, og så videre, indtil vi får den sorterede liste.
Flet sorteringskoncept
Lad os se følgende Merge-sorteringsdiagram.
Vi har opdelt den givne liste i de to halvdele. Listen kunne ikke opdeles i lige store dele, det betyder slet ikke noget.
Merge sortering kan implementeres ved hjælp af to måder - top-down tilgang og bottom-up tilgang. Vi bruger top-down-tilgangen i ovenstående eksempel, som oftest bruges Merge sort.
Bottom-up tilgangen giver jo mere optimering, som vi vil definere senere.
Hoveddelen af algoritmen er, hvordan vi kombinerer de to sorterede underlister. Lad os flette de to sorterede flettelister.
- A: [ 2 , 4, 7, 8]
- B: [ 1 , 3, 11]
- sorteret : tom
Først observerer vi det første element i begge lister. Vi finder, at B's første element er mindre, så vi tilføjer dette i vores sorterede liste og går videre i B-listen.
- A: [ 2 , 4, 7, 8]
- B: [1, 3 , elleve]
- Sorteret: 1
Nu ser vi på det næste par af elementer 2 og 3. 2 er mindre, så vi tilføjer det til vores sorterede liste og går videre til listen.
- A: [ 2 , 4, 7, 8]
- B: [1, 3 , elleve]
- Sorteret: 1
Fortsæt denne proces, og vi ender med den sorterede liste med {1, 2, 3, 4, 7, 8, 11}. Der kan være to særlige tilfælde.
java hello world eksempel
Hvad hvis begge underlister har samme elementer - I så fald kan vi flytte en af underlisten og tilføje elementet til den sorterede liste. Teknisk set kan vi gå videre i både underlisten og tilføje elementerne til den sorterede liste.
Vi har intet element tilbage i én underliste. Når vi løber tør for i en underliste, skal du blot tilføje elementet i den anden efter hinanden.
Vi skal huske, at vi kan sortere elementet i en hvilken som helst rækkefølge. Vi sorterer den givne liste i stigende rækkefølge, men vi kan nemt sortere i faldende rækkefølge.
Implementering
Fletningssorteringsalgoritmen implementeres ved at bruge top-down tilgangen. Det kan se lidt svært ud, så vi vil uddybe hver enkelt step-in detaljer. Her vil vi implementere denne algoritme på to typer samlinger - heltalselementliste (typisk brugt til at introducere sortering) og et brugerdefineret objekt (et mere praktisk og realistisk scenarie).
Sortering Array
Algoritmens hovedkoncept er at opdele (under)liste i halvdele og sortere dem rekursivt. Vi fortsætter processen, indtil vi ender med lister, der kun har ét element. Lad os forstå følgende funktion til division -
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)
Vores primære fokus på at opdele listen i underdele, før sorteringen sker. Vi skal have heltalsværdien, så vi bruger //-operatoren til vores indekser.
Lad os forstå ovenstående procedure ved at følge trinene.
- Første trin er at oprette kopier af lister. Den første liste indeholder listerne fra [venstre_indeks,...,midt] og den anden fra [midt+1,?,højre_indeks] .
- Vi krydser begge kopier af listen ved at bruge markøren, vælger den mindste værdi af de to værdier og tilføjer dem til den sorterede liste. Når vi tilføjer elementet til listen, og vi bevæger os fremad i den sorterede liste uanset.
- Tilføj de resterende elementer i den anden kopi til det sorterede array.
Lad os implementere flettesorteringen i Python-programmet.
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 >= 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)> Sortering af brugerdefinerede objekter
Vi kan også sortere de brugerdefinerede objekter ved at bruge Python klasse. Denne algoritme ligner næsten ovenstående, men vi skal gøre den mere alsidig og bestå sammenligningsfunktionen.
Vi vil oprette en brugerdefineret klasse, Bil og tilføje et par felter til den. Vi foretager få ændringer i nedenstående algoritme for at gøre den mere alsidig. Det kan vi gøre ved at bruge lambda-funktionerne.
streng concat java
Lad os forstå følgende eksempel.
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('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)> Optimering
Vi kan forbedre ydeevnen af flettesorteringsalgoritmen. Lad os først forstå forskellen mellem top-down og bottom-up flettesorteringen. Bottom-up tilgangen sorterer elementerne i tilstødende lister iterativt, hvor top-down tilgangen opdeler listerne i to halvdele.
Den givne liste er [10, 4, 2, 12, 1, 3], i stedet for at opdele den i [10], [4], [2], [12], [1], [3] - vi deler ind i underlisterne, som måske allerede er sorteret: [10, 4], [2], [1, 12], [3] og nu er klar til at sortere dem.
Merge sort er en ineffektiv algoritme i både tid og rum for de mindre underlister. Så indsættelsessortering er en mere effektiv algoritme end flettesorteringen for de mindre underlister.
Konklusion
Merge sort er populær og effektiv algoritme. Det er en mere effektiv algoritme til de store lister. Det afhænger ikke af de uheldige beslutninger, der fører til dårlige køretider.
Der er én stor ulempe ved fusionssorten. Den bruger den ekstra hukommelse, der bruges til at gemme de midlertidige kopier af lister, før de flettes. Men Merge sort er meget udbredt i softwaren. Dens ydeevne er hurtig og giver det fremragende resultat.
Vi har diskuteret flettesorteringskonceptet kort og implementeret det både på simpel heltalsliste og på brugerdefinerede objekter via en lambda-funktion, der bruges til sammenligning.