Samenvoegsortering is vergelijkbaar met het snelle sorteeralgoritme en werkt aan het concept van verdeel en heers. Het is een van de meest populaire en efficiënte sorteeralgoritmen. Het is het beste voorbeeld van de categorie van verdeel en heers-algoritmen.
Het verdeelt de gegeven lijst in twee helften, roept zichzelf op voor de twee helften en voegt vervolgens de twee gesorteerde helften samen. Wij definiëren de samenvoegen() functie die wordt gebruikt om twee helften samen te voegen.
De sublijsten worden keer op keer in helften verdeeld totdat we elk het enige element krijgen. Vervolgens combineren we het paar van één elementlijsten in twee elementlijsten, waarbij we ze daarbij sorteren. De gesorteerde twee elementparen worden samengevoegd in de vier elementlijsten, enzovoort totdat we de gesorteerde lijst krijgen.
Sorteerconcept samenvoegen
Laten we het volgende samenvoeg-sorteerdiagram bekijken.
We hebben de gegeven lijst in twee helften verdeeld. De lijst kan niet in gelijke delen worden verdeeld, het maakt helemaal niets uit.
Samenvoegsortering kan op twee manieren worden geïmplementeerd: een top-downbenadering en een bottom-upbenadering. In het bovenstaande voorbeeld gebruiken we de top-downbenadering, waarbij samenvoegsortering het vaakst wordt gebruikt.
De bottom-up benadering biedt de meer optimalisatie die we later zullen definiëren.
Het belangrijkste onderdeel van het algoritme is de manier waarop we de twee gesorteerde sublijsten combineren. Laten we de twee gesorteerde samenvoeglijsten samenvoegen.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- gesorteerd: leeg
Eerst observeren we het eerste element van beide lijsten. We ontdekken dat het eerste element van B kleiner is, dus voegen we dit toe aan onze gesorteerde lijst en gaan verder in de B-lijst.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , elf]
- Gesorteerd: 1
Nu kijken we naar het volgende paar elementen 2 en 3. 2 is kleiner, dus we voegen het toe aan onze gesorteerde lijst en gaan verder naar de lijst.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , elf]
- Gesorteerd: 1
Ga door met dit proces en we krijgen de gesorteerde lijst van {1, 2, 3, 4, 7, 8, 11}. Er kunnen twee bijzondere gevallen zijn.
ascii-tabel java
Wat als beide sublijsten dezelfde elementen bevatten? In dat geval kunnen we één sublijst verplaatsen en het element aan de gesorteerde lijst toevoegen. Technisch gezien kunnen we verder gaan in beide sublijsten en de elementen aan de gesorteerde lijst toevoegen.
We hebben geen element meer in één sublijst. Als we geen sublijst meer hebben, voegt u eenvoudigweg het element van de tweede na de andere toe.
We moeten niet vergeten dat we het element in willekeurige volgorde kunnen sorteren. We sorteren de gegeven lijst in oplopende volgorde, maar we kunnen eenvoudig in aflopende volgorde sorteren.
Implementatie
Het samenvoegsorteeralgoritme wordt geïmplementeerd met behulp van de top-downbenadering. Het kan er enigszins moeilijk uitzien, dus we zullen elke stap-in details uitwerken. Hier zullen we dit algoritme implementeren op twee soorten verzamelingen: de lijst met integer-elementen (meestal gebruikt om sorteren te introduceren) en een aangepast object (een praktischer en realistischer scenario).
Sorteermatrix
Het belangrijkste concept van een algoritme is om de (sub)lijst in twee helften te verdelen en deze recursief te sorteren. We gaan door met het proces totdat we lijsten krijgen die slechts één element bevatten. Laten we de volgende functie voor deling begrijpen:
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)
Onze primaire focus is om de lijst in subdelen te verdelen voordat het sorteren plaatsvindt. We moeten de gehele waarde verkrijgen, dus gebruiken we de // operator voor onze indices.
Laten we de bovenstaande procedure begrijpen door de stappen te volgen.
- De eerste stap is het maken van kopieën van lijsten. De eerste lijst bevat de lijsten van [linker_index,...,midden] en de tweede van [midden+1,?,right_index] .
- We doorkruisen beide exemplaren van de lijst met behulp van de aanwijzer, selecteren de kleinere waarde van de twee waarden en voegen ze toe aan de gesorteerde lijst. Zodra we het element aan de lijst hebben toegevoegd, gaan we hoe dan ook verder in de gesorteerde lijst.
- Voeg de resterende elementen in de andere kopie toe aan de gesorteerde array.
Laten we de samenvoegsortering in het Python-programma implementeren.
Python-programma
# 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)> Aangepaste objecten sorteren
We kunnen de aangepaste objecten ook sorteren met behulp van de Python klas. Dit algoritme is vrijwel gelijk aan het bovenstaande, maar we moeten het veelzijdiger maken en de vergelijkingsfunctie doorstaan.
We zullen een aangepaste klasse, Auto, maken en er een paar velden aan toevoegen. We brengen enkele wijzigingen aan in het onderstaande algoritme om het veelzijdiger te maken. We kunnen dit doen door de lambda-functies te gebruiken.
Laten we het volgende voorbeeld begrijpen.
Python-programma
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)> Optimalisatie
We kunnen de prestaties van het samenvoeg-sorteeralgoritme verbeteren. Laten we eerst eens kijken naar het verschil tussen de top-down en bottom-up samenvoegsortering. Bij de bottom-up-benadering worden de elementen van aangrenzende lijsten iteratief gesorteerd, terwijl bij de top-down-benadering de lijsten in twee helften worden opgedeeld.
De gegeven lijst is [10, 4, 2, 12, 1, 3], in plaats van deze op te splitsen in [10], [4], [2], [12], [1], [3] - we verdelen in de sublijsten die mogelijk al gesorteerd zijn: [10, 4], [2], [1, 12], [3] en zijn nu klaar om ze te sorteren.
Samenvoegsortering is een inefficiënt algoritme in zowel tijd als ruimte voor de kleinere sublijsten. Invoegsortering is dus een efficiënter algoritme dan de samenvoegsortering voor de kleinere sublijsten.
Conclusie
Samenvoegsortering is een populair en efficiënt algoritme. Het is een efficiënter algoritme voor de grote lijsten. Het hangt niet af van eventuele ongelukkige beslissingen die tot slechte looptijden leiden.
Er kleeft één groot nadeel aan het samenvoegen. Het maakt gebruik van het extra geheugen dat wordt gebruikt om de tijdelijke kopieën van lijsten op te slaan voordat ze worden samengevoegd. Samenvoegen wordt echter veel gebruikt in de software. De prestaties zijn snel en leveren een uitstekend resultaat op.
kandidaat sleutel
We hebben het samenvoeg-sorteerconcept in het kort besproken en dit zowel op een eenvoudige lijst met gehele getallen als op aangepaste objecten geïmplementeerd via een lambda-functie die ter vergelijking wordt gebruikt.