Die Zusammenführungssortierung ähnelt dem Schnellsortierungsalgorithmus, da sie auf dem Konzept des Teilens und Eroberns basiert. Es ist einer der beliebtesten und effizientesten Sortieralgorithmen. Es ist das beste Beispiel für die Kategorie „Teile und herrsche“ von Algorithmen.
Es teilt die gegebene Liste in zwei Hälften, ruft sich für die beiden Hälften auf und führt dann die beiden sortierten Hälften zusammen. Wir definieren die verschmelzen() Funktion zum Zusammenführen zweier Hälften.
Die Unterlisten werden immer wieder in zwei Hälften geteilt, bis wir jeweils nur noch ein Element erhalten. Dann kombinieren wir das Paar aus einer Elementliste zu zwei Elementlisten und sortieren sie dabei. Die sortierten zwei Elementpaare werden in den vier Elementlisten zusammengeführt und so weiter, bis wir die sortierte Liste erhalten.
Sortierkonzept zusammenführen
Sehen wir uns das folgende Zusammenführungssortierungsdiagramm an.
Wir haben die angegebene Liste in zwei Hälften geteilt. Die Liste lässt sich nicht in gleiche Teile teilen, das spielt überhaupt keine Rolle.
Die Zusammenführungssortierung kann auf zwei Arten implementiert werden – Top-Down-Ansatz und Bottom-Up-Ansatz. Im obigen Beispiel verwenden wir den Top-Down-Ansatz, bei dem es sich um die am häufigsten verwendete Zusammenführungssortierung handelt.
Der Bottom-up-Ansatz bietet die weitere Optimierung, die wir später definieren werden.
Der Hauptteil des Algorithmus besteht darin, wie wir die beiden sortierten Unterlisten kombinieren. Lassen Sie uns die beiden sortierten Zusammenführungslisten zusammenführen.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- sortiert: leer
Zunächst betrachten wir das erste Element beider Listen. Wir stellen fest, dass das erste Element von B kleiner ist, also fügen wir es unserer sortierten Liste hinzu und gehen in der B-Liste weiter.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , elf]
- Sortiert: 1
Jetzt schauen wir uns das nächste Elementpaar 2 und 3 an. 2 ist kleiner, also fügen wir es unserer sortierten Liste hinzu und gehen weiter zur Liste.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , elf]
- Sortiert: 1
Setzen Sie diesen Vorgang fort und am Ende erhalten wir die sortierte Liste von {1, 2, 3, 4, 7, 8, 11}. Es kann zwei Sonderfälle geben.
Objekt für JSON in Java
Was passiert, wenn beide Unterlisten dieselben Elemente enthalten? In diesem Fall können wir eine der Unterlisten verschieben und das Element zur sortierten Liste hinzufügen. Technisch gesehen können wir in beiden Unterlisten weitermachen und die Elemente zur sortierten Liste hinzufügen.
Wir haben kein Element mehr in einer Unterliste. Wenn wir in einer Unterliste aufgebraucht sind, fügen wir einfach nacheinander das Element der zweiten hinzu.
Wir sollten bedenken, dass wir die Elemente in beliebiger Reihenfolge sortieren können. Wir sortieren die angegebene Liste in aufsteigender Reihenfolge, können aber auch problemlos in absteigender Reihenfolge sortieren.
Implementierung
Der Zusammenführungssortierungsalgorithmus wird mithilfe des Top-Down-Ansatzes implementiert. Es kann etwas schwierig aussehen, deshalb werden wir die einzelnen Schritte im Detail ausarbeiten. Hier implementieren wir diesen Algorithmus für zwei Arten von Sammlungen – die Liste ganzzahliger Elemente (wird normalerweise zur Einführung der Sortierung verwendet) und ein benutzerdefiniertes Objekt (ein praktischeres und realistischeres Szenario).
Array sortieren
Das Hauptkonzept des Algorithmus besteht darin, (Unter-)Listen in Hälften zu teilen und sie rekursiv zu sortieren. Wir setzen den Prozess fort, bis wir Listen erhalten, die nur ein Element enthalten. Lassen Sie uns die folgende Funktion für die Division verstehen:
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)
Unser Hauptaugenmerk liegt darauf, die Liste vor der Sortierung in Unterteile zu unterteilen. Wir müssen den ganzzahligen Wert erhalten, also verwenden wir den //-Operator für unsere Indizes.
Lassen Sie uns das obige Verfahren anhand der folgenden Schritte verstehen.
- Der erste Schritt besteht darin, Kopien von Listen zu erstellen. Die erste Liste enthält die Listen von [left_index,...,mitte] und der zweite von [mitte+1,?,right_index] .
- Wir durchlaufen beide Kopien der Liste mit dem Zeiger, wählen den kleineren der beiden Werte aus und fügen ihn der sortierten Liste hinzu. Sobald wir das Element zur Liste hinzugefügt haben, bewegen wir uns in der sortierten Liste trotzdem vorwärts.
- Fügen Sie die verbleibenden Elemente in der anderen Kopie zum sortierten Array hinzu.
Lassen Sie uns die Zusammenführungssortierung im Python-Programm implementieren.
Python-Programm
# 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)> Benutzerdefinierte Objekte sortieren
Wir können die benutzerdefinierten Objekte auch mithilfe von sortieren Python Klasse. Dieser Algorithmus ähnelt fast dem oben genannten, wir müssen ihn jedoch vielseitiger machen und die Vergleichsfunktion übergeben.
Wir erstellen eine benutzerdefinierte Klasse, Car, und fügen ihr einige Felder hinzu. Wir nehmen am folgenden Algorithmus einige Änderungen vor, um ihn vielseitiger zu machen. Wir können dies tun, indem wir die Lambda-Funktionen verwenden.
Lassen Sie uns das folgende Beispiel verstehen.
Python-Programm
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)> Optimierung
Wir können die Leistung des Merge-Sort-Algorithmus verbessern. Lassen Sie uns zunächst den Unterschied zwischen der Zusammenführungssortierung von oben nach unten und von unten nach oben verstehen. Der Bottom-Up-Ansatz sortiert die Elemente benachbarter Listen iterativ, während der Top-Down-Ansatz die Listen in zwei Hälften aufteilt.
Die gegebene Liste ist [10, 4, 2, 12, 1, 3], anstatt sie in [10], [4], [2], [12], [1], [3] zu zerlegen – wir teilen in die Unterlisten, die möglicherweise bereits sortiert sind: [10, 4], [2], [1, 12], [3] und nun bereit sind, sie zu sortieren.
in Java-Regex
Die Zusammenführungssortierung ist für die kleineren Unterlisten ein zeitlich und räumlich ineffizienter Algorithmus. Daher ist die Einfügungssortierung für die kleineren Unterlisten ein effizienterer Algorithmus als die Zusammenführungssortierung.
Abschluss
Zusammenführungssortierung ist ein beliebter und effizienter Algorithmus. Es ist ein effizienterer Algorithmus für große Listen. Es kommt nicht auf unglückliche Entscheidungen an, die zu schlechten Laufzeiten führen.
Es gibt einen großen Nachteil bei der Zusammenführungssortierung. Es nutzt den zusätzlichen Speicher, der zum Speichern der temporären Kopien von Listen vor dem Zusammenführen verwendet wird. Allerdings wird die Zusammenführungssortierung in der Software häufig verwendet. Seine Leistung ist schnell und liefert ein hervorragendes Ergebnis.
Wir haben das Konzept der Zusammenführungssortierung kurz besprochen und implementieren es sowohl für einfache Ganzzahllisten als auch für benutzerdefinierte Objekte über eine zum Vergleich verwendete Lambda-Funktion.