L'ordinamento di unione è simile all'algoritmo di ordinamento rapido poiché funziona sul concetto di divide et impera. È uno degli algoritmi di ordinamento più popolari ed efficienti. È il miglior esempio della categoria di algoritmi divide et impera.
Divide l'elenco fornito nelle due metà, richiama se stesso per le due metà e quindi unisce le due metà ordinate. Definiamo il unisci() funzione utilizzata per unire due metà.
Le sottoliste vengono divise più e più volte a metà finché non otteniamo un solo elemento ciascuna. Quindi combiniamo la coppia di elenchi di un elemento in due elenchi di elementi, ordinandoli nel processo. Le due coppie di elementi ordinate vengono unite nelle quattro liste di elementi e così via fino ad ottenere la lista ordinata.
Unisci il concetto di ordinamento
Vediamo il seguente diagramma di ordinamento Merge.
Abbiamo diviso l'elenco fornito in due metà. L'elenco non può essere diviso in parti uguali, non ha alcuna importanza.
L'ordinamento di unione può essere implementato utilizzando due modi: approccio dall'alto verso il basso e approccio dal basso verso l'alto. Usiamo l'approccio top down nell'esempio precedente, che è l'ordinamento di unione utilizzato più spesso.
L'approccio bottom-up fornisce la maggiore ottimizzazione che definiremo in seguito.
La parte principale dell'algoritmo è il modo in cui combiniamo le due sottoliste ordinate. Uniamo i due elenchi di unione ordinati.
- UN : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- ordinato: vuoto
Innanzitutto osserviamo il primo elemento di entrambi gli elenchi. Troviamo che il primo elemento della B è più piccolo, quindi lo aggiungiamo al nostro elenco ordinato e andiamo avanti nell'elenco B.
- UN : [ 2 , 4, 7, 8]
- B: [1, 3 , undici]
- Ordinati: 1
Ora guardiamo la prossima coppia di elementi 2 e 3. 2 è più piccolo quindi lo aggiungiamo al nostro elenco ordinato e andiamo avanti nell'elenco.
- UN : [ 2 , 4, 7, 8]
- B: [1, 3 , undici]
- Ordinati: 1
Continua questo processo e ci ritroveremo con l'elenco ordinato di {1, 2, 3, 4, 7, 8, 11}. Possono esserci due casi particolari.
java lungo fino a int
Cosa succede se entrambi i sottoelenchi hanno gli stessi elementi - In tal caso, possiamo spostare uno dei sottoelenchi e aggiungere l'elemento all'elenco ordinato. Tecnicamente, possiamo andare avanti in entrambi i sottolisti e aggiungere gli elementi all'elenco ordinato.
Non abbiamo più elementi in una sottolista. Quando esauriamo il sottoelenco in un sottoelenco aggiungiamo semplicemente l'elemento del secondo uno dopo l'altro.
Dovremmo ricordare che possiamo ordinare l'elemento in qualsiasi ordine. Ordiniamo l'elenco fornito in ordine crescente ma possiamo facilmente ordinarlo in ordine decrescente.
Implementazione
L'algoritmo di merge sort viene implementato utilizzando l'approccio top-down. Può sembrare leggermente difficile, quindi elaboreremo i dettagli di ogni passaggio. Qui implementeremo questo algoritmo su due tipi di raccolte: elenco di elementi interi (tipicamente utilizzato per introdurre l'ordinamento) e un oggetto personalizzato (uno scenario più pratico e realistico).
obj in Java
Matrice di ordinamento
Il concetto principale dell'algoritmo è dividere la (sotto)elenco a metà e ordinarli in modo ricorsivo. Continuiamo il processo finché non arriviamo a liste che hanno un solo elemento. Comprendiamo la seguente funzione per la divisione -
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)
Il nostro obiettivo principale è dividere l'elenco in sottoparti prima che avvenga l'ordinamento. Dobbiamo ottenere il valore intero, quindi utilizziamo l'operatore // per i nostri indici.
Comprendiamo la procedura di cui sopra seguendo i passaggi.
- Il primo passo è creare copie degli elenchi. Il primo elenco contiene gli elenchi da [indice_sinistra,...,centro] e il secondo da [centro+1,?,indice_destra] .
- Attraversiamo entrambe le copie dell'elenco utilizzando il puntatore, selezioniamo il valore più piccolo dei due valori e li aggiungiamo all'elenco ordinato. Una volta aggiunto l'elemento all'elenco, andiamo avanti comunque nell'elenco ordinato.
- Aggiungi gli elementi rimanenti nell'altra copia all'array ordinato.
Implementiamo l'ordinamento di unione nel programma Python.
Programma 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)> Ordinamento di oggetti personalizzati
Possiamo anche ordinare gli oggetti personalizzati utilizzando il file Pitone classe. Questo algoritmo è quasi simile al precedente ma dobbiamo renderlo più versatile e superare la funzione di confronto.
Creeremo una classe personalizzata, Car e vi aggiungeremo alcuni campi. Apportiamo alcune modifiche all'algoritmo seguente per renderlo più versatile. Possiamo farlo utilizzando le funzioni lambda.
Comprendiamo il seguente esempio.
Programma 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)> Ottimizzazione
Possiamo migliorare le prestazioni dell'algoritmo di ordinamento del merge. Per prima cosa capiamo la differenza tra l'ordinamento di unione top-down e bottom-up. L'approccio dal basso verso l'alto ordina iterativamente gli elementi degli elenchi adiacenti mentre l'approccio dall'alto verso il basso suddivide gli elenchi in due metà.
L'elenco fornito è [10, 4, 2, 12, 1, 3], invece di scomporlo in [10], [4], [2], [12], [1], [3] - lo dividiamo nei sottoelenchi che potrebbero già essere ordinati: [10, 4], [2], [1, 12], [3] e ora sono pronti per ordinarli.
L'ordinamento di unione è un algoritmo inefficiente sia nel tempo che nello spazio per i sottoelenchi più piccoli. Pertanto, l'ordinamento per inserimento è un algoritmo più efficiente rispetto all'ordinamento di unione per i sottoelenchi più piccoli.
Conclusione
L'ordinamento di unione è un algoritmo popolare ed efficiente. È un algoritmo più efficiente per gli elenchi di grandi dimensioni. Non dipende da eventuali decisioni sfortunate che portano a tempi di autonomia scadenti.
C'è un grande demerito nell'ordinamento di fusione. Utilizza la memoria aggiuntiva utilizzata per archiviare le copie temporanee degli elenchi prima di unirli. Tuttavia l'ordinamento di unione è ampiamente utilizzato nel software. Le sue prestazioni sono veloci e producono risultati eccellenti.
Abbiamo discusso in breve il concetto di merge sort e lo abbiamo implementato sia su semplici elenchi di interi che su oggetti personalizzati tramite una funzione lambda utilizzata per il confronto.